Turkish Mathematical Olympiad

Let $G = \bigcup_{i=1}^{k} G_i$ be a graph that can be vertex-colored using not more than $2009$ colors where each $G_i$ is either a star or $e(G_i) \le 17$ for $1 \le i \le k$. We want to find the maximum possible value of $k$.

Suppose that $G_i$ is a star for $1 \le i \le j$, and $G_i$ satisfies $e(G_i) \le 17$ for $j+1 \le i \le k$ where $0 \le j \le k$. If at least $j+10$ colors are needed to color $\bigcup_{i=1}^{j} G_i$, then we must have $\binom{j+10}{2} \le 17j$ and since $(j - \frac{15}{2})^2 + \frac{135}{4} \le 0$, this gives a contradiction. Hence it is possible to color $\bigcup_{i=1}^{j} G_i$ using at most $j+9$ colors. Since we might

need at most one more color every time we add a star, we conclude that $G$ can
be colored using not more than $k + 9$ colors.

On the other hand, if $k \ge 9$, there is a case when $k+9$ is needed: We use $9$ $G_i$s to form a $C_{18}$ and then use $k-9$ stars to complete this to a $C_{k+9}$.

We conclude that greatest value of $k$ for which $2009$ colors suffice is $2000$.