Skip to main content
2 of 2
fixed a typo in the definition of degeneracy
Louis D
  • 1.7k
  • 13
  • 27

Replacing maximum degree with degeneracy in Brooks' theorem

This is related to a previous question that I asked.

The degeneracy of a graph G, denoted degen(G), is given by max{δ(H):HG}. It is well known that for all graphs G, χ(G)degen(G)+1Δ(G)+1. Brooks' theorem characterizes graphs with χ(G)=Δ(G)+1.

Is there a characterization of graphs G with χ(G)=degen(G)+1?

The example given by Mikhail Tikhomirov in response to my previous question (where χ(G)=4 and degen(G)=3) suggests that if there is a characterization, it will be much more complicated than the one given by Brooks' theorem. So any properties which imply χ(G)=degen(G)+1 would be interesting.

Note that the degeneracy plus 1 is also referred to as the coloring number, and is denoted col(G). So my question can also be phrased as "Is there a characterization of graphs G with χ(G)=col(G)?"

Louis D
  • 1.7k
  • 13
  • 27