Optimal path and cycle decompositions of dense quasirandom graphs

Stefan Glock, Daniela Kuhn, Deryk Osthus

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
155 Downloads (Pure)

Abstract

Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let 0n,p. Let odd(G) be the number of odd degree vertices in G. Then a.a.s. the following hold:(i)G can be decomposed into ⌊Δ(G)/2⌋ cycles and a matching of size odd(G)/2.(ii)G can be decomposed into max {odd(G)/2, ⌈Δ(G)/2⌉} paths.(iii)G can be decomposed into ⌈Δ(G)/2⌉ linear forests. Each of these bounds is best possible. We actually derive (i)-(iii) from 'quasirandom' versions of our results. In that context, we also determine the edge chromatic number of a given dense quasirandom graph of even order. For all these results, our main tool is a result on Hamilton decompositions of robust expanders by Kühn and Osthus.

Original languageEnglish
Pages (from-to)88-108
Number of pages21
JournalJournal of Combinatorial Theory. Series B
Volume118
Early online date28 Jan 2016
DOIs
Publication statusPublished - 1 May 2016

Keywords

  • Cycle decomposition
  • Linear arboricity
  • Overfull subgraph conjecture
  • Path decomposition
  • Quasirandom graph
  • Robust expander

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Optimal path and cycle decompositions of dense quasirandom graphs'. Together they form a unique fingerprint.

Cite this