###### 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.