# Upper bound for chromatic number, related with degree

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 !

• 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. Oct 26, 2015 at 11:43
• @hardmath Yes, I have solved it, following bof's hint. Thanks for your comment !
– Hans
Oct 26, 2015 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?
• 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 ?