Suppose you have a simple graph $G$ with max degree $\Delta(G)=k-1$ and chromatic index $\chi’(G)=k$. Let $v\in V(G)$ be a vertex incident with edges $a, b\in E(G)$. Can you find an edge $k$-coloring which is proper except for having $a, b$ of the same color? And what if you assume the restriction that $|V(G)|=k$? If the answer is “yes”, how do you prove it? There is a generalization of this which I would like to prove, but I guess this is a good starting point.
An edge coloring problem
EGME
- 1k
- 8
- 14