Replacing maximum degree with degeneracy in Reed's conjecture

Question

Reed's conjecture says that $\chi(G)\leq \lceil\frac{\omega(G)+\Delta(G)+1}{2}\rceil$. One can think of $\lceil\frac{\omega(G)+\Delta(G)+1}{2}\rceil$ as the (rounded-up) average of the trivial lower bound and the trivial upper-bound on $\chi(G)$. An equally trivial upper-bound on $\chi(G)$ is $\mathrm{degen}(G)+1$ where $\mathrm{degen}(G)=\max\{\delta(H): H\subseteq G\}$ and clearly $\mathrm{degen}(G)\leq \Delta(G)$.

So I was just wondering if there are any simple examples which would disprove the stronger statement $\chi(G)\leq \lceil\frac{\omega(G)+\mathrm{degen}(G)+1}{2}\rceil$?

Answer 1

Here's a reasonably simple counterexample.

Take $C_9$, and label its vertices $v_0, \ldots, v_8$ along the cycle. Let $\mathcal{I}$ be the family of all independent sets of $C_9$ of size $3$. $\chi(C_9) = 3$, further:

Lemma. For any 3-coloring of $C_9$ there exists $I \in \mathcal{I}$ with vertices of all three colors.

Proof. Let $f$ be the 3-coloring. Following the sequence of colors $f(v_0), f(v_2), \ldots, f(v_8), f(v_1), \ldots, f(v_7), f(v_0)$, we can find a pair of vertices at distance $2$ with different colors, WLOG assume $f(v_0) = 0$, $f(v_2) = 1$. If any of $v_4, \ldots, v_7$ has color $2$, then we are done. Otherwise, $f(v_4), \ldots, f(v_7) \in \{0, 1\}$, and $f(v_4) = f(v_6) \neq f(v_5) = f(v_7)$. Since $f(v_1) = 2$, we can take $v_1, v_4, v_7$.

Now, create a graph $G$ as follows: take $C_9$, and for each $I \in \mathcal{I}$ create a new vertex $u_I$ connected to all elements of $I$.

• $w(G) = 2$, since there are no triangles (ensured by not connecting new vertices to vertices adjacent in $C_9$);

• $degen(G) = 3$. Indeed, for any subgraph $H \subseteq G$, $\delta(H) \leq 3$ if any $u_I \in H$, and $\delta(H) \leq 2$ if $H \subseteq C_9$.

• $\chi(G) = 4$. The upper bound is obvious. The lower bound follows from the lemma above: assume that $G$ is 3-colorable, then for $I = \{a, b, c\}$ produced by the lemma (for the 3-coloring restricted to $C_9$), the color of $u_I$ has to be distinct from (distinct) colors of $a, b, c$, a contradiction.

This violates the strong conjecture: $4 > \lceil \frac{2 + 3 + 1}{2}\rceil$.