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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.