Minimal ramsey graphs with many vertices of small degree

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

Options

Minimal ramsey graphs with many vertices of small degree