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