Polynomial η-boundedness of M_t-free graphs

Status solved high confidence

Conjecture 1.20 asserts that for every integer $t \geq 3$, $M_t$-free graphs (graphs containing no induced matching of size $t$) are polynomially $\eta$-bounded. This was resolved by Ai, Liu, Xu, and Zhou in arXiv:2403.19737 (published in the Electronic Journal of Combinatorics, 2025), who proved that any graph $G$ without an induced matching of size $t$ satisfies $\eta(G) \leq \omega(G)^{3t-3+o(1)}$, establishing polynomial $\eta$-boundedness for all $t \geq 1$ and explicitly resolving the conjecture of Hajebi, Li, and Spirkl.

Cited literature (1)

• proof Piercing Independent Sets in Graphs without Large Induced Matching (2025)
  Jiangdong Ai, Hong Liu, Zixiang Xu, Qiang Zhou · The Electronic Journal of Combinatorics · arXiv:2403.19737

  Proves that any graph $G$ without an induced matching of size $t$ satisfies $\eta(G) \leq \omega(G)^{3t-3+o(1)}$, fully resolving Conjecture 1.20 by establishing polynomial $\eta$-boundedness for all $M_t$-free graph classes.

Reviewer notes. Conjecture 1.20 is fully resolved by arXiv:2403.19737 (Ai, Liu, Xu, Zhou; EJC 2025), posted just two months after the source paper appeared as a final journal version. The EJC article explicitly states it resolves the conjecture of Hajebi, Li, and Spirkl. The internal reference arXiv:2507.06169 concerns treewidth obstructions and is unrelated to this conjecture.

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