MathDB

Chen–Raspaud conjecture

For every integer k≥2k\ge 2, every graph GG with odd girth og⁡(G)≥2k+1\operatorname{og}(G)\ge 2k+1 and maximum average degree mad⁡(G)<2+1/k\operatorname{mad}(G)<2+1/k admits a (2k+1:k)(2k+1:k)-coloring; that is, there is an assignment of a kk-element subset of {1,…,2k+1}\{1,\ldots,2k+1\} to each vertex of GG such that adjacent vertices receive disjoint subsets. Here mad⁡(G)=max⁡H⊆G, V(H)≠∅2∣E(H)∣/∣V(H)∣\operatorname{mad}(G)=\max_{H\subseteq G,\,V(H)\ne\varnothing}2|E(H)|/|V(H)|.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Kneser-graph homomorphism formulation

    For every integer k≥2k\ge 2, every graph GG with og⁡(G)≥2k+1\operatorname{og}(G)\ge 2k+1 and mad⁡(G)<2+1/k\operatorname{mad}(G)<2+1/k admits a graph homomorphism G→KG(2k+1,k)G\to KG(2k+1,k), where KG(2k+1,k)KG(2k+1,k) is the Kneser graph whose vertices are the kk-element subsets of {1,…,2k+1}\{1,\ldots,2k+1\} and whose edges join disjoint subsets.

    source: A Proof of the Chen--Raspaud Conjecture

Sources & referencesView supporting material

Primary source

arXiv

Additional references

graph-colouringgraph-theory

Progress summary

Refreshed
Claimed solved

A new unrefereed manuscript claims to prove the conjecture in every dimension covered by it, but the proof has not yet been independently verified.

The Chen–Raspaud conjecture predicts a specific fractional-colouring of graphs satisfying sparse-graph and odd-girth conditions, for every integer k≥2k \ge 2. A complete proof would settle a broad family of sparse-graph colouring questions.

Known results

  • k=2k=2: Chen and Raspaud.
  • k=3k=3: Łyczek, Nazarczuk, and Rzążewski.
  • k=4k=4: Choi.

August 2026 claimed proof

Qi Wu and Yong Lu’s manuscript, submitted August 15, claims that every graph GG with og⁡(G)≥2k+1\operatorname{og}(G) \ge 2k+1 and mad⁡(G)<2+1/k\operatorname{mad}(G) < 2+1/k admits a (2k+1:k)(2k+1:k)-colouring, equivalently a homomorphism to KG(2k+1,k)KG(2k+1,k), for all k≥2k \ge 2. The authors report that ChatGPT 5.6 Pro assisted with strategies, proof checking, and exposition; the manuscript is unrefereed, with no independent verification found.

Current status (as of August 2026): The cases k=2k=2, k=3k=3, and k=4k=4 are reported as known, while the all-kk theorem remains an unverified claim rather than a settled result.

Sources

Solutions 0

No solutions have been posted yet.