Linear Ramsey Numbers

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

Text Ramsey-linear-2.pdf - Submitted version Download (275kB) | Preview

Abstract

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:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3100227