Journal article
The weak 3-flow conjecture and the weak circular flow
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.
Language: | English |
---|---|
Year: | 2012 |
Pages: | 521-529 |
ISSN: | 10960902 and 00958956 |
Types: | Journal article |
DOI: | 10.1016/j.jctb.2011.09.003 |
ORCIDs: | Thomassen, Carsten |