Skip to main content
2 of 2
added 2 characters in body
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Counterexamples are, for example, complete graphs with even number $2k$ of vertices. If we manage to color such a graph with $2k$ colors, then all vertices have different colors, and from each vertex of color, say, $s$, there is exactly one edge of each color except $s$. Therefore total number of edges of each color is $(2k-1)/2$, this is not possible.

Your observation on clique number is correct: each clique either contains at least two edges and at most one vertex, or it contains unique edge and at most 2 vertices, or it contains only vertices. All cases are clear.

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459