# Upper bound on $\chi(G)$ for a triangle-free graph

I'm struggling with the following question;

For every graph $G$ such that $K_3 \not\subseteq G$ (i.e. $G$ does not contain a triangle), prove that $\chi(G) \leq 2\sqrt{n} +1$ (where $\chi(G)$ denotes the chromatic number).

Any hints? I really cannot see the connection between the triangle-free nature of $G$ and a chromatic number being bounded above by $O(\sqrt{n})$.

Start with a lemma: Every triangle-free graph contains an independent set of size $\sqrt{n}$. This can be proven by degree considerations: If there exists a vertex of degree $\geq \sqrt{n}$, consider it's neighbors. Otherwise the maximum degree is at most $\sqrt{n}-1$ and apply the greedy algorithm.
To prove the result, apply induction. Let $S$ be an independent set of size $\sqrt{n}$, and let $H=G\setminus S$. Then $H$ is triangle free and has at most $n-\sqrt{n}$ vertices, and so can be properly colored using at most $2\sqrt{n-\sqrt{n}}+1$ colors. Conclude that $G$ can be properly colored using $2\sqrt{n}+1$ colors.
• Could you elaborate on the case where the maximum degree is at most $\sqrt{n}-1$ and the greedy algorithm? (yes, I realize this is a year and a half later :P) Feb 15, 2015 at 21:54
• @ctlaltdefeat: Suppose that the largest independent set $S$ has size $m<\sqrt{n}$, and the maximum degree is at most $\sqrt{n}-1$. For $v\in S$ let $N(v)$ be $v$ together with all of its neighbors; $$|N(v)|\le\sqrt{n}, so \left|\bigcup_{v\in S}N(v)\right|\le m\sqrt{n}<n\;,$$ so there is a vertex $u$ not in $\bigcup_{v\in S}N(v)$. Then $S\cup\{u\}$ is independent, contradicting the maximality of $S$. Feb 16, 2015 at 1:57