Is the genus of the complete graph on $n$ vertices the smallest genus among graphs with the same chromatic number?

124 Views Asked by At

If $K_n$ is the complete graph on $n$ vertices and $G$ is a graph with chromatic number $n$ then how can we show that $\gamma(K_n)\leq \gamma(G)$ is not always true where $\gamma(x)$ is the genus of a graph. The sequence of the chromatic number of a surface of genus $n$ is A000934 while the genus of the complete graph is here A000933 which becomes much larger than the Heawood sequence. Is this correct?

1

There are 1 best solutions below

0
On

The claim is false. The sequence of the chromatic number of a surface of genus $n$ is A000934 while the genus of the complete graph is here A000933 which becomes much larger than the Heawood sequence disproving the claim.