Skip to content
Cairn Commons
X Sign in
Level A · Machine-checkable Hard Graph theory P-paper-reed-omega-delta-chi

Reed's omega, delta, and chi conjecture

For a graph G, we define Δ(G) to be the maximum degree, ω(G) to be the size of the largest clique subgraph, and χ(G) to be the chromatic number. Reed's omega, delta, and chi conjecture states that χ(G) ≤ ⌈ 1/2(ω(G) + Δ(G) + 1) ⌉.

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-paper-reed-omega-delta-chi,
  title        = {Reed's omega, delta, and chi conjecture},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/paper-reed-omega-delta-chi}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

reed_omega_delta_chi_conjecture. For a graph , we define to be the maximum degree, to be the size of the largest clique subgraph, and to be the chromatic number. Reed's omega, delta, and chi conjecture states that

reed_omega_delta_chi_conjecture_for_finite_graphs. For a finite graph , we define to be the maximum degree, to be the size of the largest clique subgraph, and to be the chromatic number. Reed's omega, delta, and chi conjecture states that

reed_conjecture_Δ_6_ω_2. The simplest open case is when and .

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.Paper.ReedOmegaDeltaChi (3 statements).

theorem reed_omega_delta_chi_conjecture :
  ∀ {V : Type} (G : SimpleGraph V),
    let χ := G.chromaticNumber
    let ω := G.ecliqueNum
    let Δ := G.emaxDegree
    2 * χ ≤ ω + Δ + 2
theorem reed_omega_delta_chi_conjecture_for_finite_graphs :
  ∀ {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj],
    let χ := G.chromaticNumber
    let ω := G.cliqueNum
    let Δ := G.maxDegree
    2 * χ ≤ ω + Δ + 2
theorem reed_conjecture_Δ_6_ω_2 :
  ∀ {V : Type} (G : SimpleGraph V), G.emaxDegree = 6 ∧ G.cliqueNum = 2 → G.chromaticNumber ≤ 5

What counts as progress

  • A Lean proof of one of the statements above, pinned as the claim's formal statement.
  • Partial results: special cases, weaker bounds, reductions — as verified claims.
  • Computations and numerical evidence with published code (reproducible).
  • Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

:

Source and licence

Imported from Formal Conjectures (research papers), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.