Let G be a graph of degree n with degree sequence $d_1 ≥ d_2 ≥ d_3 ≥ ⋯d_n$. Show that the chromatic number satisfies:
$$χ(G) ≤ 1 + max_i(min(d_i , i − 1))$$
Hint: Assign colors to vertices in order of non-increasing degrees such that no conflict arises. This will produce a valid coloring.
Any ideas on how to prove this question? I don't exactly understand what the formula is saying.
Best Answer
I found the following answer to my question:
This proof is mentioned in the question previously asked here: Proof of $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$ in graph theory