I've seen this question being asked on here before but I haven't been able to solve this problem with the provided answers. If it is of any use I've been able to prove that $G$ has an independent set $S:|S|= \lfloor \sqrt{n} \rfloor$ but I don't really know what I can do with this. How can I go about proving this? I'm only looking for some ideas, not a full proof.

Edit: As you can see in the conversation below a person was kind enough to try to help me but I didn't get anywhere. Are there any further tips that can be given such that I can prove this theorem without actually giving away all of it? Thus far I've been unable to solve this problem and thus far all other students in my class have failed as well.

  • $\begingroup$ Have you looked at this? $\endgroup$ – noedne Apr 2 at 9:16
  • $\begingroup$ Yes, so when attempting to prove this with induction we assume that $G\setminus S$ can be colored with no more than $\lfloor2\sqrt{n-\lfloor \sqrt{n} \rfloor}\rfloor$ colors, and so $G$ can be colored with $\lfloor2\sqrt{n-\lfloor \sqrt{n} \rfloor}\rfloor + 1$ colors but I don't know how to continue. $\endgroup$ – David Apr 2 at 9:33
  • 1
    $\begingroup$ Do you need the $+1$? And doesn't that achieve the desired result? $\endgroup$ – noedne Apr 2 at 9:37
  • 1
    $\begingroup$ Thank you very much, I think I've managed to figure it out. I will post my full solution a bit later. $\endgroup$ – David Apr 2 at 10:06
  • $\begingroup$ I thought I had it but actually I didn't. I've spent a couple of hours again trying to figure out a way to make sense of all this but I do not get anywhere. I can only prove that $G$ can be colored with $\lfloor 2\sqrt{n} \rfloor + 1$ colors where the $+1$ comes from giving $S$ a new color. $\endgroup$ – David Apr 2 at 18:34

An independent set of size $\sqrt n$ is not really the best we can do. Rather, we can show that in any graph on $\binom{k+1}{2}$ (rather than $k^2$) vertices, there is either a triangle or an independent set of size $k$ - this is a special case of Ramsey's theorem, but you can also try to prove this independently if you like.

Even this bound is not best possible, but better results are hard to prove.

This argument gives us an independent set of size $\sqrt{2n}$ in the limit as $n \to \infty$, so intuitively, we should be able to prove a bound on the chromatic number of about $\sqrt{2n}$ as well. Try doing this in the same way as you did before; even if you get another pesky $+1$ at the end, it shouldn't stop you, because $\sqrt{2n}$ is better than $2\sqrt n$.

  • $\begingroup$ Thank you, I will look into this a bit later today and try to solve it. I'll let you know how it went. $\endgroup$ – David Apr 12 at 16:27

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.