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

  • 3
    What is $d$? Is the graph $d$-regular instead of $k$-regular?2011-11-28
  • 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