Computer Science – Discrete Mathematics
Scientific paper
2010-03-30
Discrete Mathematics 312/2 (2012) pp. 476--478
Computer Science
Discrete Mathematics
9 pages
Scientific paper
10.1016/j.disc.2011.09.020
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)} \leq \lfloor \frac{\Delta(G)}{2} \rfloor$, and that this bound is best possible.
Mkrtchyan Vahan V.
Steffen Eckhard
No associations
LandOfFree
Measures of edge-uncolorability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Measures of edge-uncolorability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Measures of edge-uncolorability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-80958