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.
References
- Bogdan Alecu, Aistis Atminas, Vadim Lozin and Viktor Zamaraev, “Graph classes with linear Ramsey numbers”, arXiv:1910.12109 (2020).
Progress summary
Never refreshed
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.