Linear Ramsey Numbers

Atminas, Aistis, Lozin, Vadim and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2018) Linear Ramsey Numbers. .

[img] Text
Ramsey-linear-2.pdf - Submitted version

Download (275kB) | Preview


The Ramsey number RX(p, q) for a class of graphs X is the minimum n such that every graph in X with at least n vertices has either a clique of size p or an independent set of size q. We say that Ramsey number is linear in X if there is a constant k such that RX(p, q) ≤k(p+q) for all p, q. In the present paper we conjecture that Ramsey number is linear in X if and only if the co-chromatic number is bounded in X and determine Ramsey numbers for several classes of graphs that verify the conjecture.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 07 Sep 2020 08:05
Last Modified: 18 Jan 2023 23:35
DOI: 10.1007/978-3-319-94667-2_3
Related URLs: