Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
What is $d$? Is the graph $d$-regular instead of $k$-regular? –  Srivatsan Nov 28 '11 at 21:31
5  
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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.