# Replacing maximum degree with degeneracy in Reed's conjecture

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$$?

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$$.