eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2017-10-26
Vol. 19 no. 3
Graph Theory
10.23638/DMTCS-19-3-7
659
journal article
On path-cycle decompositions of triangle-free graphs
Andrea JimĂ©nez
Yoshiko Wakabayashi
In this work, we study conditions for the existence of length-constrained
path-cycle decompositions, that is, partitions of the edge set of a graph into
paths and cycles of a given minimum length. Our main contribution is the
characterization of the class of all triangle-free graphs with odd distance at
least $3$ that admit a path-cycle decomposition with elements of length at
least $4$. As a consequence, it follows that Gallai's conjecture on path
decomposition holds in a broad class of sparse graphs.
https://dmtcs.episciences.org/659/pdf
Mathematics - Combinatorics
05C38, 05C05, 05C10, 05C75
G.2.2