Optimal path and cycle decompositions of dense quasirandom graphs

Research output: Contribution to journalArticle

Standard

Harvard

APA

Vancouver

Author

Bibtex

@article{54fe21b52f82433ba95e2ad9c871bfa7,
title = "Optimal path and cycle decompositions of dense quasirandom graphs",
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{\"u}hn and Osthus.",
keywords = "Cycle decomposition, Linear arboricity, Overfull subgraph conjecture, Path decomposition, Quasirandom graph, Robust expander",
author = "Stefan Glock and Daniela Kuhn and Deryk Osthus",
year = "2016",
month = may,
day = "1",
doi = "10.1016/j.jctb.2016.01.004",
language = "English",
volume = "118",
pages = "88--108",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Optimal path and cycle decompositions of dense quasirandom graphs

AU - Glock, Stefan

AU - Kuhn, Daniela

AU - Osthus, Deryk

PY - 2016/5/1

Y1 - 2016/5/1

N2 - 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.

AB - 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.

KW - Cycle decomposition

KW - Linear arboricity

KW - Overfull subgraph conjecture

KW - Path decomposition

KW - Quasirandom graph

KW - Robust expander

UR - http://www.scopus.com/inward/record.url?scp=84961267231&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2016.01.004

DO - 10.1016/j.jctb.2016.01.004

M3 - Article

AN - SCOPUS:84961267231

VL - 118

SP - 88

EP - 108

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -