Linear Ramsey numbers

Aistis Atminas, Vadim Lozin*, Viktor Zamaraev

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings
EditorsHon Wai Leong, Costas Iliopoulos, Wing-Kin Sung
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319946665
Publication statusPublished - 2018
Externally publishedYes
Event29th International Workshop on Combinatorial Algorithms, IWOCA 2018 - Singapore, Singapore
Duration: 16 Jul 201819 Jul 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10979 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference29th International Workshop on Combinatorial Algorithms, IWOCA 2018


Dive into the research topics of 'Linear Ramsey numbers'. Together they form a unique fingerprint.

Cite this