All graphs are finite, simple and undirected. A cycle is simple and has length at least three. A cycle-and-edge partition of a graph is a partition of its edge set into parts, each of which is the edge set of a cycle of or a single edge of . The decomposition cost of is the least number of parts in a cycle-and-edge partition of . A tree on vertices has decomposition cost . The Erdős-Gallai cycle decomposition conjecture asserts that there is an absolute constant such that every graph on vertices has decomposition cost at most .
The conjecture appears in the 1966 paper of Erdős, Goodman and Pósa. That paper records the upper bound on the decomposition cost of a graph on vertices. In 2014 Conlon, Fox and Sudakov improved this bound to . Write for the number of iterations of the logarithm needed to bring to at most . Bucić and Montgomery then proved the bound . There are complete bipartite graphs on vertices with decomposition cost at least . Conlon, Fox and Sudakov proved a linear bound, with high probability, for binomial random graphs. For fixed , Girão, Granet, Kühn and Osthus proved that every sufficiently large graph on vertices with minimum degree at least has decomposition cost at most . Akbari, Aloni, Beikmohammadi and Clow proved the bound for graphs on vertices of maximum degree at most four. When the cycles and edges may overlap, Pyber proved that of them suffice to cover the edges of every graph on vertices.
The preprint proves the Erdős-Gallai cycle decomposition conjecture, as its Theorem 1.1. The preprint derives from it that every graph on vertices whose degrees are all even has an edge partition into at most cycles, with the constant of Theorem 1.1, a consequence that the Lean library does not contain.
The Lean library CycleDecomposition proves Theorem 1.1. The Lean library takes no result as a hypothesis. Lean has checked every result of the Lean library, and the Lean library is therefore the reference. Each result on these pages is stated as the Lean library states it and is linked to the Lean declaration behind it. Where the preprint states a result differently, the preprint’s statement is given beside the Lean library’s. The preprint is a guide only: it gives the results their order and their names.
CycleDecomposition is a Lean library: 22 items, in eight groups. Each has a page written by OctoInform, listed below.
No item matches.