Claw‐decompositions and tutte‐orientations
János Barát, Carsten Thomassen · Journal of Graph Theory · 2006
Abstract We conjecture that, for each tree T, there exists a natural number kT such that the following holds: If G is a kT‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K1,3 (the claw), this holds if and only if there exists a (smallest) natural number kt such that every kt‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that kt = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006