## DIMACS TR: 98-04

## Measurements of Uncolorability

### Author: Eckhard Steffen

**
ABSTRACT
**

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