Measurements of edge-uncolorability Original Research Article

Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let ck be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r3=|E|−c3 and r2=23|E|−c2. We show that on one side r3 and r2 bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r3 and ω are arbitrarily far apart, and show that for each 1⩽c<2 there is a cubic graph such that ω⩾cr3. For k=2,3, let ζk denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other.