Decomposing highly edge-connected graphs into paths of any given length

Author(s)

Botler, F. ; Mota, G. O. ; Oshiro, M. T. I. ; Wakabayashi, Y.

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 122, p. 508-542, JAN 2017.
• Web of Science Citations: 7

Abstract

In 2006, Barat and Thomassen posed the following conjecture: for each tree T, there exists a natural number k(T) such that, if G is a k(T)-edge-connected graph and vertical bar E(G)vertical bar is divisible by vertical bar E(T)vertical bar, then G admits a decomposition into copies of T. This conjecture was verified for stars, some bistars, paths of length 3, 5, and 2(r) for every positive integer r. We prove that this conjecture holds for paths of any fixed length. (C) 2016 Elsevier Inc. All rights reserved. (AU)

• FAPESP's process: 13/20733-2 - Extremal and probabilistic combinatorics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• 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
• FAPESP's process: 13/11431-2 - Extremal and probabilistic combinatorics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 11/08033-0 - Decomposition of a graph into paths: structural and algorithmic aspects
• Grantee: Fábio Happ Botler
• Support Opportunities: Scholarships in Brazil - Doctorate
• FAPESP's process: 14/01460-8 - Graph decompositions
• Grantee: Fábio Happ Botler
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate