Title: On measures of edge-uncolorability of cubic graphs: A brief survey and some new results,
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 {\em 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.