Math Conjectures

Reed's Δ\Delta–ω\omega Chromatic Conjecture

OPENMajorConjectureProposed 1998 · Standard version

Canonical statement

Every finite simple graph GG satisfies
χ(G)≤⌈Δ(G)+1+ω(G)2⌉, \chi(G)\leq \left\lceil\frac{\Delta(G)+1+\omega(G)}2\right\rceil,
where Δ(G)\Delta(G) is the maximum degree and ω(G)\omega(G) the clique number.
View source LaTeX
Every finite simple graph \(G\) satisfies
\[
  \chi(G)\leq
  \left\lceil\frac{\Delta(G)+1+\omega(G)}2\right\rceil,
\]
where \(\Delta(G)\) is the maximum degree and \(\omega(G)\) the clique
number.
GRAPH-017:[Reed1998OmegaDelta][KingReed2014][BonamyPerrettPostle2020Reed]
Graph theoryCombinatorics

Notes

Greedy coloring gives χ(G)≤Δ(G)+1\chi(G)\le\Delta(G)+1 for every graph GG with maximum degree Δ(G)\Delta(G), while the clique number supplies the lower bound χ(G)≥ω(G)\chi(G)\ge\omega(G). In 1998 Reed conjectured that the chromatic number always lies at most halfway between these two classical quantities: χ(G)≤⌈(Δ(G)+1+ω(G))/2⌉\chi(G)\le\lceil(\Delta(G)+1+\omega(G))/2\rceil [Reed1998OmegaDelta]. The rounding is necessary, and the conjectured bound would interpolate sharply between the greedy bound, attained by cliques and odd cycles, and the clique bound.

Substantial partial results are known. Reed's original paper already established that some convex combination (1−ε)(Δ+1)+εω(1-\varepsilon)(\Delta+1)+\varepsilon\omega bounds χ\chi for a small positive ε\varepsilon [Reed1998OmegaDelta], and King and Reed later gave a simpler route to such a bound [KingReed2014]. Bonamy, Kelly, Nelson, and Postle showed that graphs without large cliques have chromatic number at most a fraction of Δ\Delta [BonamyPerrettPostle2020Reed]. The fractional analogue of the conjecture is known, and the exact bound has been verified for several graph classes.

The full conjecture, the precise rounded bound for arbitrary graphs, remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.