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 language | English |
---|---|
Journal | Journal of Combinatorial Theory. Series B |
Volume | 102 |
Issue number | 2 |
Pages (from-to) | 521-529 |
ISSN | 0095-8956 |
DOIs | |
Publication status | Published - 2012 |
Keywords
- Orientations modulo k
- Star decomposition
- 3-Flow conjecture