Decomposing graphs into paths of fixed length (Q2448964): Difference between revisions

The paper addresses the following conjecture of Barát and Thomassen: For each tree \(T\) there is a natural number \(k = k(T)\) such that any graph \(G\) that is \(k\)-edge connected with \(| E(T)| \) dividing \(| E(G)| \) can be decomposed into edge disjoint copies of the tree \(T\). This conjecture is verified for any tree \(P\) that is a path of length \(p\) a power of \(2\). The proof involves vertex colorings and multi-edge-colorings of a multi-graph \(G\) with edge-connectivity at least \(\alpha(p, m)\), where each edge has at most \(m\) colors and no vertex sees a color more than once.