0
$\begingroup$

I need to find chromatic number of graph $G$ obtained from $K_{2019}$ , by removing one Hamiltonian cycle from it. I already did this example for even $n$. Now if $V(G)=\{1,2,...,n\}$, and if $n$ is even, "odd" vertices are forming graph $K_{\frac{n}{2}}$, so chromatic number was $\ge \frac{n}{2}$. Then it was easy to find one proper coloring with $\frac{n}{2}$ colors. But now, for $2019$, "even" vertices are forming graph $K_{1009}$ so chromatic number is $\ge 1009$. Now, I am not sure that there exists proper coloring with $1009$ colors, so chromatic number should be $1010$. But how to prove that there is not proper coloring with $1009$ colors?

$\endgroup$
2
$\begingroup$

Let the vertices of the complete graph $K_n$ be located at the vertices of a regular $n$-gon. Then the edges of $K_n$ are all possible diagonals of $n$-gon and all its sides. Now remove all sides of the $n$-gon. We obtain our graph $G$. Let $n=2019$. Suppose the vertices of $G$ are painted in $1009$ colors. Then we find three vertices colored in the same color. But then this coloring is not proper.

$\endgroup$
1
  • $\begingroup$ Thanks to @MishaLavrov for the helpful observation. $\endgroup$
    – kabenyuk
    Sep 13 '21 at 15:16
1
$\begingroup$

Suppose a colouring with 1009 colours is possible.
Take 1008 consecutive even points. They have 1008 different colours.
There is a gap of 5 between the ends. Either of the middle two can complete a set of 1009, so they are the same colour.
Likewise, all adjacent points are the same colour, which gives a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.