17th 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 $\left(\genfrac{}{}{0ex}{}{j+10}{2}\right)\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$.