# A lower bound on the chromatic number of regular graphs

Given a $k$-regular simple graph $G$ of $n$ vertices, show that $\chi(G) \geq n/(n-d)$, where $\chi(G)$ is the chromatic number of $G$.

I'm rather unsure how to start this one, however my initial approach to it was induction on n number of vertices. However unless I'm missing something (most likely) my inductive argument seems to fail as I cannot justify my inductive step (given our IH, how do I progress from there to complete inductive step?). And since it is an inequality I don't think double counting is an applicable approach (although I haven't tried but that is my guess).

-
What is $d$? Is the graph $d$-regular instead of $k$-regular? – Srivatsan Nov 28 '11 at 21:31
Dude, these are questions off my problem sets, so you're a student in my class. If you use answers you get off math.SE in the problem set you submit tomorrow, please be sure to cite them as such, OK? I won't deduct marks... – Daniel Moskovich Nov 28 '11 at 23:59

• Show that any independent set of $G$ contains at most $n-d$ vertices, i.e., show $\alpha(G) \leqslant n-d$.
• Do you know any inequality relating $\alpha(G)$ and $\chi(G)$?
(I am assuming that the graph is $d$-regular instead of $k$-regular.)