A Modular Inductive Proof of the Chen-Raspaud Conjecture via Graph Classification
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912168617705472 |
|---|---|
| author | Fiedorowicz, Michał |
| author_facet | Fiedorowicz, Michał |
| contents | It is conjectured by Chen and Raspaud that for each integer $k \ge 2$, any graph $G$ with \[ \mathrm{mad}(G) < \frac{2k+1}{k} \quad\text{and}\quad \mathrm{odd\text{-}girth}(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17925 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Modular Inductive Proof of the Chen-Raspaud Conjecture via Graph Classification Fiedorowicz, Michał Combinatorics It is conjectured by Chen and Raspaud that for each integer $k \ge 2$, any graph $G$ with \[ \mathrm{mad}(G) < \frac{2k+1}{k} \quad\text{and}\quad \mathrm{odd\text{-}girth}(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. |
| title | A Modular Inductive Proof of the Chen-Raspaud Conjecture via Graph Classification |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.17925 |