# Proof of $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$ in graph theory

I am learning a coloring theorem in graph theory:

If a graph $G$ has degree sequence $d_1\geq\cdots\geq d_n$, then $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$.

The proof in the book consists of 4 sentences:

1. We apply greedy coloring to the vertices in nonincreasing order of degree.
2. When we color the $i$th vertex $v_i$, it has at most $\min\{d_i,i-1\}$ earlier neighbors, wo at most this many colors appear on its earlier neighbors.
3. Hence the color we assign to $v_i$ is at most $1+\min\{d_i,i-1\}$.
4. This holds for each vertex, so we maximize over $i$ to obtain the upper bound on the maximum color used.

The greedy coloring relative to a vertex ordering $v_1,\cdots,v_n$ of $V(G)$ is obtained by coloring vertices in the order $v_1,\cdots,v_n$, assigning to $v_i$ the smallest-indexed color not already used on its lower-indexed neighbors.

I don't understand the first sentence in the proof: Where do we use the nonincreasing order of degree in the rest of the proof?

• The vertices are ordered in that way so that $v_i$ has order $d_i$, I think.
– user9464
Nov 12, 2012 at 0:07

If a graph $G$ has nodes of degree $d_1, d_2, \ldots, d_n$ then $\chi(G)\le 1+\max_i \min(d_i,i-1)$.
The point of arranging the vertices with higher degree first is that this gives the best opportunity for $\max_i\min(d_i,i-1)$ to be a small number, and therefore gives a stronger bound on the chromatic number.
The key is the $\min(d_i, i-1)$. You want to prevent this from becoming large -- that is, you want to avoid any vertex where $d_i$ and $i-1$ are both large numbers. The simplest way to do that is to make sure that vertices with a large $d_i$ have as small an $i$ as you can give them -- that is, vertices with high degree should come first in the list.