3
$\begingroup$

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

  • 9
    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...2011-11-28

1 Answers 1

3

Hint.

  • 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.)