Linear Ramsey numbers and bounded co-chromatic number for finitely defined hereditary classes

Let XX be a hereditary class of graphs, meaning that it is closed under taking induced subgraphs, and suppose that XX is finitely defined, meaning that it has finitely many minimal forbidden induced subgraphs. The co-chromatic number of a graph GG is the minimum number of subsets into which V(G)V(G) can be partitioned, with each subset either a clique or an independent set. Ramsey numbers are linear in XX if there is a constant kk such that

RX(p,q)k(p+q)R_X(p,q)\leq k(p+q)

for all natural numbers pp and qq.

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

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.