Consider a simple regular graph $G$ with $n$ vertices and $E$ edges. Then, can we say that the edges can be colored equitably in $\Delta+1$ colors? By equitability is meant that a proper $\Delta+1$ coloring has either $\left\lceil\frac{E}{\Delta+1}\right\rceil$ or $\left\lfloor\frac{E}{\Delta+1}\right\rfloor$ independent edges in each color class.

I think yes. By the way, an equitable $\Delta+1$ coloring of vertices exists by Hajnál-Szemerédi theorem. I think the same would apply for edge coloring too. If not, can we at least say that each color class would have at least $\left\lfloor\frac{E}{\Delta+1}\right\rfloor$ independent edges? Thanks beforehand.


1 Answer 1


Yes. Choose any proper edge coloring with $\Delta+1$ colors (it exists by Vizing theorem). If we have two color classes with $a$ and $b$ edges respectively, $a\geqslant b+2$ (say, $a$ red eges and $b$ blue edges), consider the graph formed by these $a+b$ red or blue edges. It contains a component with more red edges then blue edges. This is a path starting and ending with a red edge. Replace the red edges in this path to blue and vice versa. Now we have $a-1$ red edges and $b+1$ blue edges. Something decreased, for example the sum of squares of the sizes of color classes. Therefore after finitely many operations we come with a situation when the sizes differ at most by 1, that we need.

  • $\begingroup$ So this reasoning can be extended to any (non-regular) graphs, right $\endgroup$
    – vidyarthi
    Commented Jul 2, 2019 at 10:41
  • $\begingroup$ @vidyarthi of course $\endgroup$ Commented Jul 2, 2019 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.