Tutte’s 5-flow conjecture from 1954 states that every bridge- less graph has a nowhere-zero 5-flow. It suffices to prove the conjecture for cyclically 6-edge-connected cubic graphs. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. This implies that every minimum counterexample to the 5-flow conjecture has oddness at least 6.
Nowhere-Zero 5-Flows On Cubic Graphs with Oddness 4 / Mazzuoccolo, Giuseppe; Steffen, Eckhard. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 85:2(2017), pp. 363-371. [10.1002/jgt.22065]
Nowhere-Zero 5-Flows On Cubic Graphs with Oddness 4
Mazzuoccolo, Giuseppe;
2017
Abstract
Tutte’s 5-flow conjecture from 1954 states that every bridge- less graph has a nowhere-zero 5-flow. It suffices to prove the conjecture for cyclically 6-edge-connected cubic graphs. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. This implies that every minimum counterexample to the 5-flow conjecture has oddness at least 6.
| File | Dimensione | Formato | |
|---|---|---|---|
|
18_11_2015_5_Flow_odd_4_revised.pdf
Accesso riservato
Dimensione
264.84 kB
Formato
Adobe PDF
|
264.84 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
