Path and cycle decompositions of dense graphs

DOI10.1112/JLMS.12455zbMATH Open1479.05300arXiv1911.05501OpenAlexW3163937182MaRDI QIDQ3384033FDOQ3384033

Authors: António Girão, Bertille Granet, Daniela Kühn, Deryk Osthus 

Publication date: 16 December 2021

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Abstract: We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on $n$ vertices can be decomposed into at most $leftlceilfracn2ightceil$ paths, while a conjecture of Haj'{o}s states that any Eulerian graph on $n$ vertices can be decomposed into at most $leftlfloorfracn-12ightfloor$ cycles. The ErdH{o}s-Gallai conjecture states that any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. We show that if $G$ is a sufficiently large graph on $n$ vertices with linear minimum degree, then the following hold. (i) $G$ can be decomposed into at most $fracn2+o(n)$ paths. (ii) If $G$ is Eulerian, then it can be decomposed into at most $fracn2+o(n)$ cycles. (iii) $G$ can be decomposed into at most $frac3n2+o(n)$ cycles and edges. If in addition $G$ satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such $G$. (iv) $G$ can be decomposed into $maxleftfracodd(G)2,fracDelta(G)2ight+o(n)$ paths, where $odd(G)$ is the number of odd-degree vertices of $G$. (v) If $G$ is Eulerian, then it can be decomposed into $fracDelta(G)2+o(n)$ cycles. All bounds in (i)-(v) are asymptotically best possible.

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

Recommendations

• Towards Gallai's path decomposition conjecture
• Path decompositions and Gallai's conjecture
• Gallai's path decomposition conjecture for graphs of small maximum degree

Mathematics Subject Classification ID

Paths and cycles (05C38) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Subgraph coverings and edge switchings
• Title not available (Why is that?)
• Path decompositions and Gallai's conjecture
• Covering the edges of a connected graph by paths
• On path decompositions of \(2 k\)-regular graphs
• An upper bound for the path number of a graph
• Gallai's conjecture for graphs of girth at least four
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Cycle packing
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• The wonderful Walecki construction
• The Representation of a Graph by Set Intersections
• An Erdős-Gallai conjecture
• The Algorithmic Aspects of the Regularity Lemma
• A proof of a conjecture of Bondy concerning paths in weighted digraphs
• Covers of Eulerian graphs
• Partitions of digraphs into paths or circuits
• What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?
• On path-cycle decompositions of triangle-free graphs
• Gallai's conjecture for disconnected graphs
• Hajós' conjecture and projective graphs
• Gallai's path decomposition conjecture for graphs of small maximum degree
• Decomposing random graphs into few cycles and edges

Cited In (13)

• An overview of graph covering and partitioning
• Decomposing toroidal graphs into circuits and edges
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Cycle factors in dense graphs
• Path decompositions of triangle-free graphs
• Towards the Erdős-Gallai cycle decomposition conjecture
• Title not available (Why is that?)
• Long cycles, heavy cycles and cycle decompositions in digraphs
• Cycle packing
• Towards the Erdős-Gallai cycle decomposition conjecture
• Cycle decompositions of pathwidth-6 graphs
• On path-cycle decompositions of triangle-free graphs
• Decomposing random graphs into few cycles and edges

This page was built for publication: Path and cycle decompositions of dense graphs

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