Measures of edge-uncolorability

Abstract

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 $\Delta (G)$-edge-colorable. The paper relates the resistance to other parameters that measure how far is a graph from being $\Delta$-edge-colorable. The first part considers regular graphs and the relation of the resistance to structural properties in terms of 2-factors. The second part studies general (multi-) graphs $G$. 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 $\frac{r(G)}{r_v(G)}\le \lfloor \frac{\Delta (G)}{2}\rfloor$, and that this bound is best possible.

9 pages

References in corpus (2)

• Tutte's 5-Flow Conjecture for Highly Cyclically Connected Cubic Graphs
• Maximum $\Delta$-edge-colorable subgraphs of class II graphs

Cited by in corpus (1)

• Generation and Properties of Snarks