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.

  • $\begingroup$ Have you tried to carry out the algorithm in the hint? That hint makes the problem rather straightforward. $\endgroup$ – Stella Biderman Dec 11 '17 at 6:19
  • $\begingroup$ 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? $\endgroup$ – Flash Dec 11 '17 at 6:24
  • $\begingroup$ 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. $\endgroup$ – Stella Biderman Dec 11 '17 at 6:26
  • $\begingroup$ 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. $\endgroup$ – Stella Biderman Dec 11 '17 at 6:31
  • 1
    $\begingroup$ Here's an idea: Assign colors to vertices in order of non-increasing degrees such that no conflict arises. $\endgroup$ – 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

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


Page 15 in here kind of answers it.

Did you find anything better?

  • $\begingroup$ I read the explanation on page 15 however, I still can't understand how that helps us prove this equation. Can you elaborate on this a bit more? $\endgroup$ – Flash Dec 12 '17 at 5:34
  • $\begingroup$ sciencedirect.com/science/article/pii/S0021980069800104 The theorem 2 on page 97 of the above article briefly talks about it as well but that explanation is too vague and so, I couldn't get much out of it either. $\endgroup$ – Flash Dec 12 '17 at 5:35
  • $\begingroup$ I found the proof in Proposition 16 in the following thesis: pdfs.semanticscholar.org/fe71/… $\endgroup$ – Flash Dec 12 '17 at 6:03

Your Answer

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

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