There is a graph G with $\nu$ vertices. We have known the degree of every vertex, defined as $d_1,d_2,...d_{\nu}$ and $d_1\geq d_2\geq...\geq d_{\nu}$. I want to show that the chromatic number $\chi(G)$ satisfies $\chi(G)\leq \underset{i}{\max \min}\{d_i+1,i\}$.

The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color.

Actually, this is a homework and I want to solve it by myself. But I've been stuck on this. Thanks for your help !

  • $\begingroup$ You been given some strong hints about how to proceed by induction, but if you want to "solve it by myself", it is going to take an effort sketching out the details with pencil-and-paper. Let us know when you have solved it. $\endgroup$ – hardmath Oct 26 '15 at 11:43
  • $\begingroup$ @hardmath Yes, I have solved it, following bof's hint. Thanks for your comment ! $\endgroup$ – Hans Oct 26 '15 at 11:52

Hint: Let $V(G)=\{v_1,v_2,\dots,v_\nu\}$ where $v_i$ is a vertex of degree $d_i.$ Now color the vertices $v_1,v_2,\dots,v_\nu$ in that order: $v_1$ first, $v_2$ second and so on. Now, at the $i^{\text{th}}$ step, when vertex $v_i$ is to be colored, what is an upper bound for the number of neighbors of $v_i$ which have already been colored?

  • 1
    $\begingroup$ Every vertex will have an upper bound $\min\{d_i,i-1\}$. Find the biggest one, just denoted as $a$, and we can use at most $a+1$ colors to complete the coloring of this graph. I guess it has been solved, right ? $\endgroup$ – Hans Oct 26 '15 at 11:07

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.