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?

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

1 Answer 1


In context "greedy coloring" must mean something like:

  1. Assign colors to vertices starting with the ones with the highest degree and ending with the ones of low degree.
  2. For each vertex, give it the lowest-numbered color that has not yet been assigned to any of its neighbors.

The nonincreasing degree order is not actually used in the prof -- without that condition, the proof would work equally well to prove:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy