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 Answers 2

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, 2021 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .