[Zurück]

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), S. 612 - 635.

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.

http://dx.doi.org/10.1002/rsa.20676

http://onlinelibrary.wiley.com/doi/10.1002/rsa.20676/abstract;jsessionid=B23EB06B8691652758D3B069049C3432.f04t01