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~\mathrm{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 relevant references or can prove or disprove this, please reply to me. Thanks in advance.


1 Answer 1


Yes. More generally, if $G$ is a graph with chromatic number $\chi(G)=n$, and if $\varphi:V(G)\to[n]=\{1,\dots,n\}$ is a proper (vertex) coloring of $G$ with $n$ colors, then for each color $c\in[n]$ there is a vertex $v\in V(G)$ such that $\varphi(v)=c$ and $\{\varphi(w):w\in N(v)\}=[n]\setminus\{c\}$.

Proof: If no such vertex $v$ existed, then all vertices of color $c$ could be recolored to obtain a proper vertex coloring with $n-1$ colors.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .