1
$\begingroup$

I am trying yo understand Vizing's proof as found in the book Graph Theory With Applications by authors Bondy and Murty.

The proof starts this way:

Proof: Let G be a simple graph. By virtue of (6.1) we need only show that $\chi' \leq \Delta$ + 1. Suppose, then, that $ \chi' > \Delta + 1$. Let C = ($E_1 , E_2 , .... , E_{\Delta+1}$) be an optimal ($\Delta$ + 1)-edge colouring of G and let u be a vertex such that c(u) < d(u). In which c(u) is the number of distinct colors of incident edges in u. d(u) is the degree of u.

Then the authors went on to show that such coloring it's not possible. I understood how they concluded that such C isn't possible. What I would like to know is why C not being possible implicates that $\chi' \leq \Delta$ + 1.

Thanks!

$\endgroup$
  • $\begingroup$ If it's not the case that $\chi'>\Delta+1$ then it must be the case that $\chi'\leq\Delta+1$. I don't think that's what you are asking, but that's how the question seems to read. Can you clarify it? Also, what are $c(u)$ and $d(u)$? $\endgroup$ – saulspatz Oct 3 '19 at 19:38
  • $\begingroup$ @saulspatz , c(u) is the number of distinct colors of incident edges in u. d(u) is the degree of u. $\endgroup$ – Victor Oct 3 '19 at 20:28
0
$\begingroup$

You have to go back to the definition of "improvement" of an edge coloring. They say that one $k$-edge coloring is an improvement on another if the sum of the number of colors at each vertex is greater. Then they say that a $k$-edge coloring is optimal if it cannot be improved on.

If the edge-chromatic number is greater than $\Delta+1$ then there must be an optimal $\Delta+1$-edge coloring that is not a proper edge coloring. Otherwise, we could keep improving any $\Delta+1$-edge coloring until the sum of the colors represented at the vertices is equal to the sum of the vertex degrees, at which point we have a proper $\Delta+1$-edge coloring.

The proof shows that an optimal $\Delta+1$-edge coloring that is not a proper edge coloring cannot exist, so $$\chi'\leq\Delta+1$$.

$\endgroup$
  • $\begingroup$ Brilliant! Thanks a lot, make perfect sense. $\endgroup$ – Victor Oct 3 '19 at 21:11
  • $\begingroup$ It was my pleasure. $\endgroup$ – saulspatz Oct 3 '19 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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