[Reed's conjecture](https://www.openproblemgarden.org/op/reeds_omega_delta_and_chi_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$?



Replacing maximum degree with degeneracy in Reed's conjecture
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$.


