Polynomial eta-boundedness of P5P_5-free graphs

Let P5P_5 be the path on five vertices. A graph is P5P_5-free if it has no induced subgraph isomorphic to P5P_5; write ω(G)\omega(G) for its clique number and η(G)\eta(G) for the minimum size of a set meeting every maximum stable set.

Polynomial P5P_5-free eta-boundedness conjecture. There exists dNd\in\mathbb{N} such that every P5P_5-free graph GG satisfies η(G)ω(G)d\eta(G)\leq\omega(G)^d.

The source states that this remains open; proving it would imply the Erdős–Hajnal conjecture for P5P_5-free graphs. The paper proves only a super-exponential bound in this setting.

Sources & referencesView supporting material

Primary source

Sepehr Hajebi, Yanjia Li and Sophie Spirkl, “Hitting all maximum stable sets in P_5-free graphs”, arXiv:2302.04986 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.