Tilings in vertex ordered graphs

Jozsef Balogh, Lina Li, Andrew Treglown

Research output: Contribution to journalArticlepeer-review

15 Downloads (Pure)

Abstract

Over recent years there has been much interest in both Turán and Ramsey properties of vertex ordered graphs. In this paper we initiate the study of embedding spanning structures into vertex ordered graphs. In particular, we introduce a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect H-tiling in an ordered graph. In the (unordered) graph setting, this problem was resolved by Kühn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009]. We use our general framework to resolve the perfect H-tiling problem for all ordered graphs H of interval chromatic number 2. Already in this restricted setting the class of extremal examples is richer than in the unordered graph problem. In the process of proving our results, novel approaches to both the regularity and absorbing methods are developed.
Original languageEnglish
Pages (from-to)171-201
Number of pages31
JournalJournal of Combinatorial Theory. Series B
Volume155
Early online date3 Mar 2022
DOIs
Publication statusPublished - Jul 2022

Bibliographical note

Funding Information:
Partially supported by NSF Grant DMS-1764123 and Arnold O. Beckman Research Award (UIUC) Campus Research Board 18132 and the Langan Scholar Fund (UIUC).Research supported by EPSRC grant EP/V002279/1.

Keywords

  • Absorbing method
  • Dirac-type problems
  • Factors
  • Ordered graphs
  • Regularity method

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Tilings in vertex ordered graphs'. Together they form a unique fingerprint.

Cite this