Nowhere-zero 3-flows and modulo k-orientations

László Miklós Lovász, Carsten Thomassen, Yezhou Wu, Cun-Quan Zhang

Research output: Contribution to journalJournal articleResearchpeer-review

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.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume103
Issue number5
Pages (from-to)587-598
ISSN0095-8956
DOIs
Publication statusPublished - 2013

Keywords

  • Integer flow
  • 3-flow
  • Tutte orientation
  • Modulo 3-orientation

Fingerprint Dive into the research topics of 'Nowhere-zero 3-flows and modulo <em>k</em>-orientations'. Together they form a unique fingerprint.

Cite this