Linear Ramsey numbers and bounded co-chromatic number for finitely defined hereditary classes
Linear Ramsey numbers and bounded co-chromatic number for finitely defined hereditary classes
Let be a hereditary class of graphs, meaning that it is closed under taking induced subgraphs, and suppose that is finitely defined, meaning that it has finitely many minimal forbidden induced subgraphs. The co-chromatic number of a graph is the minimum number of subsets into which can be partitioned, with each subset either a clique or an independent set. Ramsey numbers are linear in if there is a constant such that
for all natural numbers and .
Linear Ramsey–co-chromatic conjecture. A finitely defined hereditary class is of linear Ramsey numbers if and only if it has bounded co-chromatic number.
Classes of bounded co-chromatic number are known to have linear Ramsey numbers, but the converse fails for general hereditary classes. The conjecture asserts that the two notions coincide among finitely defined classes.
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).
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
Sign in to submit a solution.
No solutions have been posted yet.