Optimal path and cycle decompositions of dense quasirandom graphs

DOI10.1016/J.JCTB.2016.01.004zbMATH Open1332.05078arXiv1503.00494OpenAlexW1532129519MaRDI QIDQ5890517FDOQ5890517

Authors: Stefan Glock, Daniela Kühn, Deryk Osthus 

Publication date: 14 March 2016

Published in: Electronic Notes in Discrete Mathematics, Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let $0<p<1$ be constant and let $Gsim{G}_{n,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 $lfloorDelta(G)/2floor$ cycles and a matching of size $odd(G)/2$. (ii) $G$ can be decomposed into $maxodd(G)/2,lceilDelta(G)/2ceil$ paths. (iii) $G$ can be decomposed into $lceilDelta(G)/2ceil$ 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"uhn and Osthus.

Full work available at URL: https://arxiv.org/abs/1503.00494

Recommendations

• Path and cycle decompositions of dense graphs
• Decomposing random graphs into few cycles and edges
• Approximate Hamilton decompositions of random graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures

zbMATH Keywords

path decompositioncycle decompositionlinear arboricityquasirandom graphrobust expanderoverfull subgraph conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graphs.
• The NP-Completeness of Edge-Coloring
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Title not available (Why is that?)
• A constructive proof of Vizing's theorem
• How to find overfull subgraphs in graphs with large maximum degree
• Hamiltonian degree sequences in digraphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Edge-disjoint Hamilton cycles in random graphs
• Cycle packing
• Regular Graphs of High Degree are 1-Factorizable
• The linear arboricity of graphs
• Title not available (Why is that?)
• Linear arboricity of random regular graphs
• Optimal packings of Hamilton cycles in sparse random graphs
• The Representation of a Graph by Set Intersections
• Optimal covers with Hamilton cycles in random graphs
• Proof of the $1$-factorization and Hamilton Decomposition Conjectures
• Arboricity and spanning-tree packing in random graphs with an application to load balancing
• Gallai's conjecture for disconnected graphs
• Overfull conjecture for graphs with high minimum degree
• Decomposing random graphs into few cycles and edges
• Title not available (Why is that?)

This page was built for publication: Optimal path and cycle decompositions of dense quasirandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890517)