# Proof about chromatic number of graph

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.

• Have you tried to carry out the algorithm in the hint? That hint makes the problem rather straightforward. – Stella Biderman Dec 11 '17 at 6:19
• I don't exactly understand what I am trying to prove. Can you please explain what the formula is talking about and what I will be proving? – Flash Dec 11 '17 at 6:24
• Take your list of degrees. For each $i$, either save $i-1$ or $d_i$, which ever is smaller. This produces a list of numbers. Now find the largest value in that list and add one. The result is an upper bound on the chromatic number. – Stella Biderman Dec 11 '17 at 6:26
• I’ve described this theorem rather algorithmically, and that algorithm can be converted into the proof. The proof of the theorem is to give an algorithm that, at each step, either colors nodes using $d_i$ colors or $i-1$ colors, whichever is smaller, as it moves across the graph. A little careful analysis reveals that this algorithm always produces a coloring, and never uses more colors than the RHS of the inequality. – Stella Biderman Dec 11 '17 at 6:31
• Here's an idea: Assign colors to vertices in order of non-increasing degrees such that no conflict arises. – bof Dec 11 '17 at 7:03

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

• This is precisely correct! Good job figuring it out :) – Stella Biderman Dec 12 '17 at 13:14