11
$\begingroup$

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})$.

$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

Here's a sketch:

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.

$\endgroup$
2
  • $\begingroup$ 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) $\endgroup$
    – ctlaltdefeat
    Feb 15, 2015 at 21:54
  • 2
    $\begingroup$ @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$. $\endgroup$
    – Brian M. Scott
    Feb 16, 2015 at 1:57

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.