[Math] Proof about chromatic number of graph

coloringgraph theory

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:

  1. We apply greedy coloring to the vertices in non-increasing order of degree.
  2. When we color the $i^{th}$ vertex $v_i$, it has at most $\min\{d_i,i-1\}$ earlier neighbors, so 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.

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

Related Question