3
$\begingroup$

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?

$\endgroup$
1
  • $\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

2
$\begingroup$

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.

$\endgroup$

Your Answer

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