Publications in Scientific Journals:
J. Gajarsky, P. Hlinený, T. Kaiser, D. Král, M. Kupec, J. Obdrzalek, S. Ordyniak, T. Vojtech:
"First order limits of sparse graphs: Plane trees and path-width";
Random Structures and Algorithms,
50
(2017),
612
- 635.
English abstract:
Nesetř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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1002/rsa.20676
Electronic version of the publication:
http://onlinelibrary.wiley.com/doi/10.1002/rsa.20676/abstract;jsessionid=B23EB06B8691652758D3B069049C3432.f04t01
Created from the Publication Database of the Vienna University of Technology.