χ-boundedness of binary matroids excluding I_s and PG(1,2)

Conjecture 1.6 · arXiv:1806.04188

arXiv Conjecture high confidence— first stated 2019-11-13

Authors: Marthe Bonamy, Frantisek Kardos, Tom Kelly, Peter Nelson, Luke Postle

Status partial high confidence

The conjecture is verified for $s \in \{1,2,3\}$ with $k=1$ in the source paper (Corollary 5.2). Nelson and Nomoto (arXiv:2005.00089, SIAM JDM 2022) subsequently proved the case $s=4$, showing $I_4$-free and triangle-free binary matroids have critical number at most 2. The full conjecture for all $s \geq 5$ remains open.

Cited literature (2)

partial The structure of $I_4$-free and triangle-free binary matroids (2022)

Peter Nelson, Kazuhiro Nomoto · SIAM Journal on Discrete Mathematics · arXiv:2005.00089 · doi:10.1137/20M1343099

Proves a decomposition theorem for $I_4$-free and triangle-free binary matroids, establishing that such matroids have critical number at most 2, thereby settling Conjecture 1.6 for the case $s=4$.
partial The critical number of $I_{1,t}$-free triangle-free binary matroids (2020)

Peter Nelson, Kazuhiro Nomoto · arXiv preprint · arXiv:2011.06625

Proves that simple $I_{1,t}$-free and triangle-free binary matroids have bounded critical number for any $t \geq 1$, extending the bounded-critical-number programme to a broader family of excluded induced restrictions.

Reviewer notes. Conjecture 1.6 is proved for s=1,2,3 (k=1) in the source paper and for s=4 (k=2) by Nelson–Nomoto 2020 (arXiv:2005.00089, SIAM JDM 2022). The companion paper arXiv:2011.06625 handles I_{1,t}-free variants, which may not directly address I_s for large s. The conjecture for s≥5 remains open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For all $s \geq 1$ there exists an integer $k$ such that if $M$ is a simple binary matroid with no induced $I_s$-restriction or $PG(1, 2)$-restriction, then $\chi(M) \leq k$.

Context

After showing that the full matroidal Gyárfás-Sumner analogue fails (Theorem 1.3), the authors conjecture that fixing $t = 2$—that is, excluding a triangle $PG(1,2)$ rather than an arbitrary projective geometry—restores a bound on the critical number. The conjecture is verified for $s \in \{1, 2, 3\}$ by Corollary 5.2, which gives $k = 1$; new ideas are needed for larger $s$.

Source paper

The structure of binary matroids with no induced claw or Fano plane restriction
Marthe Bonamy, Frantisek Kardos, Tom Kelly, Peter Nelson, Luke Postle · 2019-11-13
https://arxiv.org/abs/1806.04188 PDF source