Skip to main content
added 2 characters in body
Source Link
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 $s$ 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 atand at most 2 vertices, or it contains only vertices. All cases are clear.

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 color $s$ 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 at at most 2 vertices, or it contains only vertices. All cases are clear.

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.

Source Link
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 color $s$ 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 at at most 2 vertices, or it contains only vertices. All cases are clear.