Publication: Research - peer-review › Journal article – Annual report year: 2012
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.
|Citations||Web of Science® Times Cited: 40|
- Orientations modulo k, Star decomposition, 3-Flow conjecture