Skip to main content
3 of 4
edited tags
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

An edge coloring problem

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.

EGME
  • 1k
  • 8
  • 14