# Equitable edge coloring of graphs

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

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.

• So this reasoning can be extended to any (non-regular) graphs, right – vidyarthi Jul 2 '19 at 10:41
• @vidyarthi of course – Fedor Petrov Jul 2 '19 at 10:51