Chromatic numbers and graph decomposition

In 2005 the Marie Curie Fellow Janos Barat and his supervisor Carsten Thomassen made the conjecture that, for every tree T, it is possible to decompose a graph of sufficiently large edge-connectivity into copies of T. Although we could not at the time verify this for any single non-trivial instance of T, we showed that, when T is the claw, the conjecture is intimately related to Tutte's 3-flow conjecture, motivated by the classical 3-color theorem of Grotzsch.

In 2010 Carsten Thomassen obtained a breakthrough, namely a proof of the so-called weak 3-flow conjecture posed in 1988 by F.Jaeger. Among the applications, the decomposition conjecture is now verified for each star.