Skip to main content
1 of 2
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 $\mathrm{degen}(G)$, is given by $\min\{\delta(H): H\subseteq G\}$. It is well known that for all graphs $G$, $\chi(G)\leq \mathrm{degen}(G)+1\leq \Delta(G)+1$. Brooks' theorem characterizes graphs with $\chi(G)=\Delta(G)+1$.

Is there a characterization of graphs $G$ with $\chi(G)=\mathrm{degen}(G)+1$?

The example given by Mikhail Tikhomirov in response to my previous question (where $\chi(G)=4$ and $\mathrm{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 $\chi(G)=\mathrm{degen}(G)+1$ would be interesting.

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

Louis D
  • 1.7k
  • 13
  • 27