Polynomial η-bound for P₅-free graphs

Status open high confidence

Conjecture 1.17 — that there exists $d\in\mathbb{N}$ with $\eta(G)\leq\omega(G)^{d}$ for every $P_5$-free graph $G$ — remains open as of May 2026. The source paper establishes only a super-exponential $\eta$-bound for $P_5$-free graphs. A 2025 Electronic Journal of Combinatorics paper resolves a related conjecture from the same paper (polynomial $\eta$-bound for graphs with no induced matching of size $t$), but this does not settle Conjecture 1.17 because $P_5$-free graphs can have arbitrarily large induced matchings.

Cited literature (1)

• partial Piercing Independent Sets in Graphs without Large Induced Matching (2025)
  Unknown · Electronic Journal of Combinatorics

  Proves $\eta(G)\leq\omega(G)^{3t-3+o(1)}$ for graphs with no induced matching of size $t$, explicitly resolving a conjecture of Hajebi, Li, and Spirkl from the source paper; does not resolve Conjecture 1.17 since $P_5$-free graphs need not have bounded induced matching number.

Reviewer notes. A closely related 2025 result in the Electronic Journal of Combinatorics resolves a conjecture of Hajebi–Li–Spirkl about graphs without large induced matchings (proving a polynomial $\eta$-bound for that class), but leaves Conjecture 1.17 open. Separately, arXiv:2512.24907 (Dec 2025) proves polynomial $\chi$-boundedness for $P_5$-free graphs (resolving a 1985 Gyárfás problem), which concerns chromatic number rather than $\eta$. No paper found proving or disproving Conjecture 1.17 in full generality.

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