Measures of edge-uncolorability

Details Measures of edge-uncolorability Measures of edge-uncolorability

2010-03-30

arxiv.org/abs/1003.5783v2

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-80958