List Ramsey numbers

We introduce a list‐coloring extension of classical Ramsey numbers. We investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For ℓ‐uniform cliques we prove that the l...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2021-01, Vol.96 (1), p.109-128
Main Authors: Alon, Noga, Bucić, Matija, Kalvari, Tom, Kuperwasser, Eden, Szabó, Tibor
Format: Article
Language:English
Subjects:
chromatic number
Exponential functions
list coloring
Ramsey theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a list‐coloring extension of classical Ramsey numbers. We investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For ℓ‐uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well known that the Ramsey number is superexponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22610