---
res:
bibo_abstract:
- There are many hard conjectures in graph theory, like Tutte's 5-flow conjecture,
and the 5-cycle double cover conjecture, which would be true in general if they
would be true for cubic graphs. Since most of them are trivially true for 3-edge-colorable
cubic graphs, cubic graphs which are not 3-edge-colorable, often called snarks,
play a key role in this context. Here, we survey parameters measuring how far
apart a non 3-edge-colorable graph is from being 3-edge-colorable. We study their
interrelation and prove some new results. Besides getting new insight into the
structure of snarks, we show that such measures give partial results with respect
to these important conjectures. The paper closes with a list of open problems
and conjectures.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: M. A.
foaf_name: Fiol, M. A.
foaf_surname: Fiol
- foaf_Person:
foaf_givenName: Guiseppe
foaf_name: Mazzuoccolo, Guiseppe
foaf_surname: Mazzuoccolo
- foaf_Person:
foaf_givenName: Eckhard
foaf_name: Steffen, Eckhard
foaf_surname: Steffen
foaf_workInfoHomepage: http://www.librecat.org/personId=15548
bibo_issue: '4'
bibo_volume: 25
dct_date: 2018^xs_gYear
dct_language: eng
dct_subject:
- Cubic graph
- Tait coloring
- Snark
- Boole coloring
- Berge's conjecture
- Tutte's 5-flow conjecture
dct_title: Measures of Edge-Uncolorability of Cubic Graphs@
...