{"docId":4010,"paperId":659,"url":"https:\/\/dmtcs.episciences.org\/659","doi":"10.23638\/DMTCS-19-3-7","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":312,"name":"Vol. 19 no. 3"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"1402.3741","repositoryVersion":3,"repositoryLink":"https:\/\/arxiv.org\/abs\/1402.3741v3","dateSubmitted":"2016-09-30 21:37:51","dateAccepted":"2017-10-26 10:17:13","datePublished":"2017-10-26 10:17:39","titles":["On path-cycle decompositions of triangle-free graphs"],"authors":["Jim\u00e9nez, Andrea","Wakabayashi, Yoshiko"],"abstracts":["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."],"keywords":["Mathematics - Combinatorics","05C38, 05C05, 05C10, 05C75","G.2.2"]}