4
$\begingroup$

This is related to a previous question that I asked.

The degeneracy of a graph $G$, denoted $\mathrm{degen}(G)$, is given by $\max\{\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)$?"

$\endgroup$
0

1 Answer 1

4
$\begingroup$

There are triangle-free $d$-degenerate graphs with chromatic number $d+1$; see http://dx.doi.org/10.1006/jctb.1999.1910 or http://dx.doi.org/10.1017/S0963548399004022 or https://arxiv.org/pdf/1310.2972.pdf. So I suspect that the desired characterisation is impossible.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .