Erdős–Hajnal polynomial Ramsey-number conjecture for hereditary classes
Erdős–Hajnal polynomial Ramsey-number conjecture for hereditary classes
Let be a proper hereditary class of graphs, meaning that is not the class of all graphs. For natural numbers and , let be the least integer such that every graph in with at least vertices has either a clique of size or an independent set of size .
Erdős–Hajnal conjecture. There are constants and such that
for every ; equivalently, Ramsey numbers grow at most polynomially in .
This is the paper’s formulation of the Erdős–Hajnal conjecture. The supplied text gives no resolution status.
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
Bogdan Alecu, Aistis Atminas, Vadim Lozin and Viktor Zamaraev, “Graph classes with linear Ramsey numbers”, arXiv:1910.12109 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.