Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The vertices are ordered in that way so that $v_i$ has order $d_i$, I think. –  Jack Nov 12 '12 at 0:07

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.