Hitting all maximum stable sets in P5-free graphs - Sepehr Hajebi

Title: Hitting all maximum stable sets in P5-free graphs

Abstract: We prove that there exists a function f such that, for every positive integer c, every graph with no induced five-vertex path contains either a clique on c+1 vertices or a set of at most f(c) vertices which intersects all maximum stable sets in G.

We also discuss the analogy with chi-boundedness and the connection to the Erdos-Hajnal conjecture.

Based on joint work with Yanjia Li and Sophie Spirkl.