Lovász, László Miklós3; Thomassen, Carsten1; Wu, Yezhou4; Zhang, Cun-Quan5
1 Department of Applied Mathematics and Computer Science, Technical University of Denmark2 Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark3 University of Cambridge4 Jiangsu Normal University5 West Virginia University
The main theorem of this paper provides partial results on some major open problems in graph theory, such as Tutteʼs 3-flow conjecture (from the 1970s) that every 4-edge connected graph admits a nowhere-zero 3-flow, the conjecture of Jaeger, Linial, Payan and Tarsi (1992) that every 5-edge-connected graph is Z3-connected, Jaegerʼs circular flow conjecture (1984) that for every odd natural number k⩾3, every (2k−2)-edge-connected graph has a modulo k-orientation, etc. It was proved recently by Thomassen that, for every odd number k⩾3, every (2k2+k)-edge-connected graph G has a modulo k-orientation; and every 8-edge-connected graph G is Z3-connected and admits therefore a nowhere-zero 3-flow. In the present paper, Thomassenʼs method is refined to prove the following: For every odd numberk⩾3, every(3k−3)-edge-connected graph has a modulo k-orientation. As a special case of the main result, every 6-edge-connected graph isZ3-connected and admits therefore a nowhere-zero 3-flow. Note that it was proved by Kochol (2001) that it suffices to prove the 3-flow conjecture for 5-edge-connected graphs.
Journal of Combinatorial Theory. Series B, 2013, Vol 103, Issue 5, p. 587-598
Integer flow; 3-flow; Tutte orientation; Modulo 3-orientation