Polynomial Rödl property for graphs close to a proper hereditary family
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.