Polynomial eta-boundedness of -free graphs
Polynomial eta-boundedness of -free graphs
Let be the path on five vertices. A graph is -free if it has no induced subgraph isomorphic to ; write for its clique number and for the minimum size of a set meeting every maximum stable set.
Polynomial -free eta-boundedness conjecture. There exists such that every -free graph satisfies .
The source states that this remains open; proving it would imply the Erdős–Hajnal conjecture for -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.