The weak 3-flow conjecture and the weak circular flow

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    We show that, for each natural number k>1, every graph (possibly with multiple edges but with no loops) of edge-connectivity at least 2k2+k has an orientation with any prescribed outdegrees modulo k provided the prescribed outdegrees satisfy the obvious necessary conditions. For k=3 the edge-connectivity 8 suffices. This implies the weak 3-flow conjecture proposed in 1988 by Jaeger (a natural weakening of Tutteʼs 3-flow conjecture which is still open) and also a weakened version of the more general circular flow conjecture proposed by Jaeger in 1982. It also implies the tree-decomposition conjecture proposed in 2006 by Bárat and Thomassen when restricted to stars. Finally, it is the currently strongest partial result on the (2+ϵ)-flow conjecture by Goddyn and Seymour.
    Original languageEnglish
    JournalJournal of Combinatorial Theory. Series B
    Volume102
    Issue number2
    Pages (from-to)521-529
    ISSN0095-8956
    DOIs
    Publication statusPublished - 2012

    Keywords

    • Orientations modulo k
    • Star decomposition
    • 3-Flow conjecture

    Cite this