| Full text | |
| Author(s): |
Total Authors: 2
|
| Affiliation: | [1] Univ Valparaiso, Fac Ingn, CIMFAV, Valparaiso - Chile
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE; v. 19, n. 3 2017. |
| Web of Science Citations: | 1 |
| Abstract | |
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. (AU) | |
| FAPESP's process: | 11/19978-5 - Embeddings of Graphs on Surfaces and the Ising Model |
| Grantee: | Andrea Patricia Jiménez Ramírez |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |