| 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.
|
