The Library
First order limits of sparse graphs : plane trees and path-width
Tools
Tools
Tools
Gajarsky, Jakub, Hlineny, Petr, Kaiser, Tomas, Králʼ, Daniel, Kupec, Martin, Obdrzalek, Jan, Ordyniak, Sebastian and Tuma, Vojtech (2017) First order limits of sparse graphs : plane trees and path-width. Random Structures and Algorithms, 50 (4). pp. 612-635. doi:10.1002/rsa.20676
|
PDF
WRAP-first-order-limits-sparse-graphs-Kral-2017.pdf - Accepted Version - Requires a PDF viewer. Download (686Kb) | Preview |
Official URL: http://dx.doi.org/10.1002/rsa.20676
Abstract
Nesetril 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.
| Item Type: | Journal Article | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Combinatorial analysis, Convergence | ||||||||||
| Journal or Publication Title: | Random Structures and Algorithms | ||||||||||
| Publisher: | John Wiley & Sons, Inc. | ||||||||||
| ISSN: | 1042-9832 | ||||||||||
| Official Date: | July 2017 | ||||||||||
| Dates: |
|
||||||||||
| Volume: | 50 | ||||||||||
| Number: | 4 | ||||||||||
| Page Range: | pp. 612-635 | ||||||||||
| DOI: | 10.1002/rsa.20676 | ||||||||||
| Status: | Peer Reviewed | ||||||||||
| Publication Status: | Published | ||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||
| Funder: | Czech Science Foundation (CSF), European Social Fund (ESF), Seventh Framework Programme (European Commission) (FP7), Engineering and Physical Sciences Research Council (EPSRC) | ||||||||||
| Grant number: | Project 14-03501S, GA14-19503S (CSF), CZ.1.07/2.3.00/3 0.0009 POSTDOC I (ESF), 2007-2013 ERC grant agreement no. 259385 (FP7), Standard Grant number EP/M025365/1 (EPSRC) | ||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
