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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.