Alecu, Bogdan, Atminas, Aistis, Lozin, Vadim and Zamaraev, Viktor 
ORCID: 0000-0001-5755-4141
(2021)
Graph classes with linear Ramsey numbers.
Discrete Mathematics, 344 (4).
p. 112307.
|
Text
linear-Ramsey-revision.pdf - Author Accepted Manuscript Download (357kB) | Preview |
Abstract
The Ramsey number $R_X(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 $R_{X}(p,q) \leq 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.
| Item Type: | Article |
|---|---|
| Additional Information: | 24 pages |
| Uncontrolled Keywords: | math.CO, math.CO |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 Mar 2021 10:52 |
| Last Modified: | 19 Jan 2023 00:18 |
| DOI: | 10.1016/j.disc.2021.112307 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3063604 |
Dimensions
Dimensions
