Factorizing regular graphs

Carsten Thomassen*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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 edgeconnectivity (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 G 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 2k2 + k.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume141
Pages (from-to)343-351
ISSN0095-8956
DOIs
Publication statusPublished - 2019

Keywords

  • Graph factors

Fingerprint Dive into the research topics of 'Factorizing regular graphs'. Together they form a unique fingerprint.

Cite this