Premium
Nowhere‐Zero 5‐Flows On Cubic Graphs with Oddness 4
Author(s) -
Mazzuoccolo Giuseppe,
Steffen Eckhard
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22065
Subject(s) - cubic graph , mathematics , conjecture , combinatorics , counterexample , graph , zero (linguistics) , discrete mathematics , petersen graph , line graph , voltage graph , linguistics , philosophy
Tutte's 5‐flow conjecture from 1954 states that every bridgeless 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.