1
$\begingroup$

In this book (I found it from other references, and it was a nice book to study.), there is an exercise that proving the following two statements.

Every graph $G$ with $m$ edges and maximum degree $k$ has a proper $(k+1)$-edge-coloring with each color used $\lfloor \frac{m}{k+1} \rfloor$ or $\lceil \frac{m}{k+1} \rceil$ times.

Every bipartite graph with maximum degree at least $k$ has a $k$-edge-coloring (not necessarily proper) in which at each vertex $v$, each color appears $\lfloor \frac{d(v)}{k} \rfloor$ or $\lceil \frac{d(v)}{k}\rceil$ times.

First one is proved by Fedor Petrov in a very elegant method.
But for second one, it seems that a quite different strategy is needed, and I have yet no idea with how to prove it.
The book only says 'Use graph transformation.' but no other hints.
Would you help me?

$\endgroup$
1
  • 2
    $\begingroup$ It would be better to start : In Exercice 8.3.27 of the book "Combinatorial Mathematics" by D.B. West (see .... (give link here)) .. Indeed, your link will perhaps not work forever and the question becomes then more difficult to understand. $\endgroup$ Nov 9, 2021 at 8:39

1 Answer 1

1
$\begingroup$

There is a proof with a very similar principle than in Petrov's proof. Take an arbitrary coloring. If the property is not respected, you have a vertex $v$ where one of the colors $c_1$ appear strictly over $⌈\frac{d(v)}{k}⌉$, and another color $c_2$ appear less or equal than $⌊\frac{d(v)}{k}⌋$ (or one which appear strictly less than $⌊\frac{d(v)}{k}⌋$ and another which appear more or equal than $⌈\frac{d(v)}{k}⌉$, but the argument is th same). Take the graph composed only of the edges colored by $c_1$ and $c_2$, and orient all $c_1$ edges in the same direction (from one part of the bipartite graph to the other) such that the arcs are leaving $v$. Same with $c_2$ but with arcs entering $v$). Follow a path in the graph starting from $v$, you cannont get stuck at $v$ as there are strictly more outcoming edges than incoming edges. Once you get stuck, you have found a node where the number of incoming arcs is strictly more than the number of outcoming arcs. It is easy to show that swapping colors in the path will strictly decrease the distances to average degree.

$\endgroup$
1
  • $\begingroup$ Nice proof! Actually, I found another proof by infinite descent about the square of the number of $c_1$ and $c_2$ edges appearing at the start and the end of such path. But I think your one is much more intuitive. Thank you. $\endgroup$
    – okw1124
    Nov 10, 2021 at 2:44

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.