TY - JOUR

T1 - Graph classes with linear Ramsey numbers

AU - Alecu, Bogdan

AU - Atminas, Aistis

AU - Lozin, Vadim

AU - Zamaraev, Viktor

N1 - Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2021/4

Y1 - 2021/4

N2 - 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 numbers are 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 if X is a hereditary class defined by finitely many forbidden induced subgraphs, then Ramsey numbers are linear in X if and only if X excludes a forest, a disjoint union of cliques and their complements. We prove the “only if” part of this conjecture and verify the “if” part for a variety of classes. We also apply the notion of linearity to bipartite Ramsey numbers and reveal a number of similarities and differences between the bipartite and non-bipartite case.

AB - 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 numbers are 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 if X is a hereditary class defined by finitely many forbidden induced subgraphs, then Ramsey numbers are linear in X if and only if X excludes a forest, a disjoint union of cliques and their complements. We prove the “only if” part of this conjecture and verify the “if” part for a variety of classes. We also apply the notion of linearity to bipartite Ramsey numbers and reveal a number of similarities and differences between the bipartite and non-bipartite case.

KW - 05C69

KW - Bounded co-chromatic number

KW - Homogeneous subgraph

KW - Linear Ramsey number

UR - http://www.scopus.com/inward/record.url?scp=85100058970&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112307

DO - 10.1016/j.disc.2021.112307

M3 - Article

AN - SCOPUS:85100058970

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 4

M1 - 112307

ER -