Path and cycle decompositions of dense graphs

DOI10.1112/JLMS.12455MaRDI QIDQ3384033zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1911.05501, https://research.birmingham.ac.uk/portal/en/publications/path-and-cycle-decompositions-of-dense-graphs(58cf93bd-af0d-46b8-8e26-f2a9a33d7093).html

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)

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.

Recommendations

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

Cites work

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

Cited in

(13)

• An overview of graph covering and partitioning
• Decomposing toroidal graphs into circuits and edges
• Cycle factors in dense graphs
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Path decompositions of triangle-free graphs
• Towards the Erdős-Gallai cycle decomposition conjecture
• scientific article; zbMATH DE number 3948320 (Why is no real title available?)
• 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)