Reed's omega, delta, and chi conjecture
Status partial high confidence
Reed's conjecture $\chi(G) \le \lceil \tfrac{1}{2}(\Delta(G)+1+\omega(G)) \rceil$ remains open for general graphs. Since the 2007 OPG posting, it has been established for quasi-line graphs and further structural classes, and the quantitative 'epsilon version' $\chi(G) \le (1-\varepsilon)(\Delta+1) + \varepsilon\,\omega$ has been progressively strengthened from $\varepsilon \approx 1/130{,}000$ to $\varepsilon = 1/26$ and reportedly further to $\varepsilon \approx 0.119$.
Cited literature (5)
-
Proves a local strengthening of Reed's conjecture for all quasi-line graphs (including line graphs), along with polytime colouring algorithms.
-
Proves Reed's conjecture for graphs in which all vertices of degree ≥ 5 form a stable set, and for graphs in which every odd induced cycle contains a vertex of degree ≤ 3.
-
Dramatically improves Reed's epsilon theorem by showing the bound χ(G) ≤ (1−ε)(Δ+1) + ε·ω holds for large Δ with ε = 1/26, up from the prior ε ≈ 1/130,000.
-
Proves a local list-colouring epsilon version of Reed's conjecture, establishing the bound under mild local density conditions.
-
Studies a Kempe-recolouring variant of Reed's conjecture; proves the analogous bound with ε = 1/2 is achievable for odd-hole-free graphs (and tight up to one colour).
Reviewer notes. The conjecture remains open for general graphs. An important unverified result: Hurley, de Verclos, and Kang (SODA 2021) reportedly improved the epsilon to ε ≈ 0.119 ('An improved procedure for colouring graphs of bounded local density'), but this paper was not fetched within the query budget and cannot be cited. The digraph analogue by Kawarabayashi–Picasarri-Arrieta (arXiv 2407.05827, 2024) is not included in since_posted as it concerns directed graphs. The SIAM journal publication of the Chudnovsky et al. paper (DOI 10.1137/110847585 per search results) is likely 2012–2013; only the 2011 arXiv submission was directly verified.
Discussion
Perhaps the two most trivial bounds on $ \chi(G) $ are $ \chi(G) \ge \omega(G) $ and $ \chi(G) \le \Delta(G) + 1 $ . The above conjecture roughly asserts that the (rounded-up) average of $ \Delta(G)+1 $ and $ \omega(G) $ should again be an upper bound on $ \chi(G) $ . The conjecture is easy to verify when $ \omega(G) $ is very large. It is trivial when $ \omega(G) \ge \Delta(G) $ , and it follows from Brook's theorem if $ \omega(G) = \Delta(G)-1 $ . On the other hand, if $ \omega(G) = 2 $ , so $ G $ is triangle free, then the conjecture is also true for $ \Delta $ sufficiently large. Indeed, Johannsen proved the much stronger fact that there exists a fixed constant $ c $ so that $ \chi(G) \le \frac{c \Delta(G)}{\log \Delta(G)} $ for every triangle free graph $ G $ . Reed showed that the conjecture holds when $ \Delta(G) = |V(G)| - 1 $ by way of matching theory. More interestingly, he proved (using probabilistc methods) that the conjecture is true provided that $ \Delta $ is sufficiently large, and $ \omega $ is sufficiently close to $ \Delta $ . More precisely, he proves the following: Theorem There exists a fixed constant $ \Delta_0 $ such that for every $ \Delta \ge \Delta_0 $ , if $ G $ is a graph of maximum degree $ \Delta $ with no clique of size $ >k $ for some $ k \ge (1 - \frac{1}{70000000}) \Delta $ then $ \chi(G) \le \frac{\Delta + 1 + k}{2} $ . It is known that the conjecture is true fractionally (that is with $ \chi(G) $ replaced by $ \chi_f(G) $ , the fractional chromatic number of~ $ G $ ).
Bibliography
-
★
[R]B. Reed, $ \omega, \Delta $ , and $ \chi $ , J. Graph Theory 27 (1998) 177-212.