Nowhere‐Zero 5‐Flows On Cubic Graphs with Oddness 4

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2017-06, Vol.85 (2), p.363-371
Main Authors: Mazzuoccolo, Giuseppe, Steffen, Eckhard
Format: Article
Language:English
Subjects:
5‐flow conjecture
cubic graphs
nowhere‐zero flows
oddness of cubic graphs
Tutte's flow conjectures
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22065