کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4657198 | 1343722 | 2012 | 9 صفحه PDF | دانلود رایگان |

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.
Journal: Journal of Combinatorial Theory, Series B - Volume 102, Issue 2, March 2012, Pages 521-529