Every 9-regular graph (possibly with multiple edges) with odd edge-connectivity > 5 can be edge-decomposed into three 3-factors. If Tutte's 3-flow conjecture is true, it also holds for all 9-regular graphs with odd edge-connectivity 5, but not with odd edge-connectivity 3. It holds for all planar 2-edge-connected 9-regular graphs, an equivalent version of the 4-color theorem for planar graphs. We address the more general question: If G is an r-regular graph, and r = kq where k, q are natural numbers > 1, can G be edge-decomposed into k q-factors? If q is even, then the decomposition exists trivially. If k, q are both odd, then we prove that the decomposition exists if G has odd edge-connectivity (size of smallest odd edge-cut) at least 3k - 2, which is satisfied if the odd edge-connectivity is at least r - 2. If q is odd and k is even, then we must require that G has an even number of vertices just to guarantee that C has a q-factor. If we want a decomposition into q-factors, then we also need the condition that, for any partition of the vertex set of G into two odd parts, there must be at least k edges between the parts. We prove that the edge-decomposition into q-factors is always possible if G has an even number of vertices and the edge-connectivity of G is at least 2k(2) + k. (C) 2019 Elsevier Inc. All rights reserved.
展开▼
