Claw‐decompositions and tutte‐orientations

Abstract

Abstract We conjecture that, for each 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 the edges of G can be divided into parts, each of which is isomorphic to T . We prove that for T = K 1,3 (the claw), this holds if and only if there exists a (smallest) natural number k t such that every k t ‐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 k t = 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