GAJARSKÝ, Jakub, Petr HLINĚNÝ, Tomáš KAISER, Daniel KRÁĽ, Martin KUPEC, Jan OBDRŽÁLEK, Sebastian ORDYNIAK and Vojtěch TŮMA. First order limits of sparse graphs: Plane trees and path-width. Random Structures & Algorithms. Wiley, 2017, vol. 50, No 4, p. 612-635. ISSN 1042-9832. Available from: https://dx.doi.org/10.1002/rsa.20676. |
Other formats:
BibTeX
LaTeX
RIS
@article{1372353, author = {Gajarský, Jakub and Hliněný, Petr and Kaiser, Tomáš and Kráľ, Daniel and Kupec, Martin and Obdržálek, Jan and Ordyniak, Sebastian and Tůma, Vojtěch}, article_number = {4}, doi = {http://dx.doi.org/10.1002/rsa.20676}, keywords = {graph limits; graphs with bounded path-width; first order limits}, language = {eng}, issn = {1042-9832}, journal = {Random Structures & Algorithms}, title = {First order limits of sparse graphs: Plane trees and path-width}, volume = {50}, year = {2017} }
TY - JOUR ID - 1372353 AU - Gajarský, Jakub - Hliněný, Petr - Kaiser, Tomáš - Kráľ, Daniel - Kupec, Martin - Obdržálek, Jan - Ordyniak, Sebastian - Tůma, Vojtěch PY - 2017 TI - First order limits of sparse graphs: Plane trees and path-width JF - Random Structures & Algorithms VL - 50 IS - 4 SP - 612-635 EP - 612-635 PB - Wiley SN - 10429832 KW - graph limits KW - graphs with bounded path-width KW - first order limits N2 - Nešetřil and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree-depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path-width has a limit modeling. ER -
GAJARSKÝ, Jakub, Petr HLINĚNÝ, Tomáš KAISER, Daniel KRÁĽ, Martin KUPEC, Jan OBDRŽÁLEK, Sebastian ORDYNIAK and Vojtěch TŮMA. First order limits of sparse graphs: Plane trees and path-width. \textit{Random Structures \&{} Algorithms}. Wiley, 2017, vol.~50, No~4, p.~612-635. ISSN~1042-9832. Available from: https://dx.doi.org/10.1002/rsa.20676.
|