Polynomial Rödl property for graphs close to a proper hereditary family
Let be a family of graphs. A graph on vertices is -close to if one can add or delete at most edges from to obtain a graph in . A hereditary family is one closed under taking induced subgraphs, and it is proper if it is not the family of all graphs.
Conjecture on hereditary families close to . For each proper hereditary family of graphs there are such that if , every graph on vertices which is -close to contains an -homogeneous set of size at least .
This conjecture extends the polynomial Rödl phenomenon from hereditary families themselves to graphs that are polynomially close to such a family. The source calls it a natural conjecture for hereditary families and provides no resolution, so its general status remains open.
References
Primary source
Matija Bucić, Jacob Fox and Huy Tuan Pham, “Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures”, arXiv:2403.08303 (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
No solutions have been posted yet.