Decomposing graphs into paths of fixed length

Research output: Contribution to journalJournal articleResearchpeer-review


Barát and Thomassen have conjectured that, for any fixed tree T, there exists a natural number k T such that the following holds: If G is a k T -edge-connected graph such that |E(T)| divides |E(G)|, then G has a T-decomposition. The conjecture is trivial when T has one or two edges. Before submission of this paper, the conjecture had been verified only for two other trees: the paths of length 3 and 4, respectively. In this paper we verify the conjecture for each path whose length is a power of 2.
Original languageEnglish
Issue number1
Pages (from-to)97-123
Publication statusPublished - 2013


Dive into the research topics of 'Decomposing graphs into paths of fixed length'. Together they form a unique fingerprint.

Cite this