10.23638/DMTCS-19-3-7
https://dmtcs.episciences.org/659
Jiménez, Andrea
Andrea
Jiménez
Wakabayashi, Yoshiko
Yoshiko
Wakabayashi
On path-cycle decompositions of triangle-free graphs
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.
episciences.org
Mathematics - Combinatorics
05C38, 05C05, 05C10, 05C75
G.2.2
arXiv.org - Non-exclusive license to distribute
2017-10-26
2017-10-26
2017-10-26
eng
journal article
arXiv:1402.3741
10.48550/arXiv.1402.3741
1365-8050
https://dmtcs.episciences.org/659/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
Vol. 19 no. 3
Graph Theory
Researchers
Students