Options
Minimal ramsey graphs with many vertices of small degree
Publikationstyp
Journal Article
Publikationsdatum
2022
Sprache
English
Institut
Enthalten in
Volume
36
Issue
3
Start Page
1503
End Page
1528
Citation
SIAM Journal on Discrete Mathematics 36 (3): 1503-1528 (2022)
Publisher DOI
Scopus ID
Given any graph H, a graph G is said to be q-Ramsey for H if every coloring of the edges of G with q colors yields a monochromatic subgraph isomorphic to H. Such a graph G is said to be minimal q-Ramsey for H if additionally no proper subgraph G′ of G is q-Ramsey for H. In 1976, Burr, Erdős, and Lovász initiated the study of the parameter sq(H), defined as the smallest minimum degree among all minimal q-Ramsey graphs for H. In this paper, we consider the problem of determining how many vertices of degree sq(H) a minimal q-Ramsey graph for H can contain. Specifically, we seek to identify graphs for which a minimal q-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property sq-abundant. Among other results, we prove that every cycle is sq-abundant for any integer q ≥ 2. We also discuss the cases when H is a clique or a clique with a pendant edge, extending previous results of Burr and co-authors and Fox and co-authors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.
Schlagworte
graph theory
minimum degrees
Ramsey graphs