A proper edge $k$-coloring of a graph is an assignment of $k$ colors to the edges of the graph so that no two adjacent edges have the same color. The smallest integer $k$ such that $G$ has a proper edge $k$-coloring is the chromatic index of $G$.

Giving a simple graph $G$, the well-known Vizing's theorem tells us that the chromatic index of any simple graph $G$ is either $\Delta(G)$ or $\Delta(G)+1$. In particular, if the chromatic index of a graph $G$ is $\Delta(G)+1$, then we say that $G$ is of class two.

Suppose that $G$ is a graph of class two and $\varphi$ is a proper edge coloring using $\Delta(G)+1$ colors. I wonder whether there always exists an edge $uv$ such that $\varphi(uv)\cup \{\varphi(e)~|~e~is~an~edge~adjacent~to~uv\}$ covers all of the $\Delta(G)+1$ colors.

I guess the answer is yes, however, cannot find any source supporting this. If anyone knows some relative references or can prove or disprove this, please reply me. Thanks in advance.

  • 2
    $\begingroup$ This is a homework level question, please try math.stackexchange.com, as this site is for researchers. $\endgroup$
    – domotorp
    Sep 26, 2021 at 15:21

1 Answer 1



Let $uv$ be an edge colored by the last color, say $\Delta+1$. If $uv$ is incidence with all colors, then it is the required edge. So the only case is that every edge colored with $\Delta+1$ is not incident with some color in $[\Delta]$, and thus it can be recolored by that color. This results an edge $\Delta$-coloring, a contradiciton.


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.