Measures of edge-uncolorability

The resistance r ( G ) of a graph G is the minimum number of edges that have to be removed from G to obtain a graph which is Δ ( G ) -edge-colorable. This paper relates the resistance to other parameters that measure how far a graph is from being Δ -edge-colorable. Let r v ( G ) be the minimum number of vertices that have to be removed from G to obtain a class 1 graph. We show that r ( G ) r v ( G ) ≤ ⌊ Δ ( G ) 2 ⌋ , and that this bound is best possible.