η-boundedness of Pₜ-free graphs

Conjecture 1.13 · arXiv:2302.04986

arXiv Conjecture high confidence— first stated 2024-01-16

Authors: Sepehr Hajebi, Yanjia Li, Sophie Spirkl

Status open high confidence

The conjecture that $P_t$-free graphs are $\eta$-bounded for every $t \geq 6$ remains open as of May 2026. The source paper establishes $\eta$-boundedness for $P_5$-free graphs (Theorem 1.12) and also resolves the $\eta$-boundedness for $H$-free graphs when $H$ is a proper induced subgraph of $P_5$. A separate 2025 result (Electronic Journal of Combinatorics) resolves a different conjecture from the same paper—bounding $h(G)$ for graphs without large induced matchings—but does not address $P_t$-free graphs for $t \geq 6$. No paper resolving or disproving Conjecture 1.13 was found in a wide web search.

Reviewer notes. No follow-up paper resolving Conjecture 1.13 was found. The conjecture is recent (2024) and widely searched; open with high confidence. The related paper arXiv:2402.11222 and the Electronic Journal of Combinatorics paper 'Piercing Independent Sets in Graphs without Large Induced Matching' (v32i1p10, 2025) resolve a different conjecture from the same source paper (about graphs with bounded induced matching number), not Conjecture 1.13.

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

Conjecture. For every integer $t\geq 6$, the class of $P_{t}$-free graphs is $\eta$-bounded.

Context

After proving $\eta$-boundedness for $P_5$-free graphs (Theorem 1.12), the authors note that it remains open whether $P_t$-free graphs are $\eta$-bounded for $t\geq 6$, and state this as a conjecture paralleling the known $\chi$-boundedness of $P_t$-free graphs for all $t$.

Source paper

Hitting all maximum stable sets in $P_5$-free graphs
Sepehr Hajebi, Yanjia Li, Sophie Spirkl · 2024-01-16
https://arxiv.org/abs/2302.04986