A Modular Inductive Proof of the Chen-Raspaud Conjecture via Graph Classification

It is conjectured by Chen and Raspaud that for each integer $k\ge 2$, any graph $G$ with $$\mathrm{m}\mathrm{a}\mathrm{d}(G)<\frac{2k+1}{k}\text{and}\mathrm{o}\mathrm{d}\mathrm{d}\text{-}\mathrm{g}\mathrm{i}\mathrm{r}\mathrm{t}\mathrm{h}(G)\ge 2k+1$$ admits a homomorphism into the Kneser graph $K(2k+1,k)$. The base cases $k=2$ and $k=3$ are known from earlier work. A modular inductive proof is provided here, in which graphs at level $k+1$ are classified into four structural classes and are shown to admit no minimal counterexamples by means of forbidden configuration elimination, a discharging argument, path-collapsing techniques, and a combinatorial embedding of smaller Kneser graphs into larger ones. This argument completes the induction for all $k\ge 2$, thus settling the Chen-Raspaud conjecture in full generality.