A snark is a cubic bridgeless graph with chromatic index $\chi'=4$. These graph are also called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other.
For $k=2,3$ let $c_i$ be the maximum size of a $k$-colorable subgraph of a cubic graph $G=(V,E)$. We consider $r_3 = |E|-c_3$ and $r_2 = \frac{2}{3}|E| - c_2$. We show that on one side $r_3$ and $r_2$ bound each other, but on the other side that the difference between them can be arbitrarily large.
We also compare them to the oddness $\omega$ of $G$, the smallest possible number of odd circuits in a 2-factor of $G$. We construct cyclically 5-edge connected graphs where $r_3$ and $\omega$ arbitrarily far apart, and show that for each $1 \leq c < 2$ there is a snark such that $\omega \geq c r_3$.
For $k=2,3$ let $\zeta_k$ denote the largest fraction of edges that can be
edge $k$-colored. We give best possible bounds for these parameters,
and relate them to each other.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-04.ps.gz
DIMACS Home Page