Lovász, László Miklós^{6}; Thomassen, Carsten^{1}; Wu, Yezhou^{4}; Zhang, Cun-Quan^{7}

Affiliations:

^{1} Department of Applied Mathematics and Computer Science, Technical University of Denmark^{2} Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark^{3} University of Cambridge^{4} Jiangsu Normal University^{5} West Virginia University^{6} University of Cambridge^{7} West Virginia University

DOI:

10.1016/j.jctb.2013.06.003

Abstract:

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.

Type:

Journal article

Language:

English

Published in:

Journal of Combinatorial Theory. Series B, 2013, Vol 103, Issue 5, p. 587-598

Keywords:

Integer flow; 3-flow; Tutte orientation; Modulo 3-orientation