Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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 ISSN 1042-9832.

[img]
Preview
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

Request Changes to record.

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:
DateEvent
July 2017Published
30 August 2016Available
31 March 2016Accepted
4 May 2016Submitted
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
Date of first compliant deposit: 20 April 2016
Date of first compliant Open Access: 30 August 2017
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:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us