论文标题
最小的拉姆西图，具有许多小度的顶点
Minimal Ramsey graphs with many vertices of small degree
论文作者
论文摘要
鉴于任何图$ h $，如果$ g $的每种颜色（$ g $）带有$ q $颜色的每种颜色会产生单色子图同构为$ h $，则据说为$ h $ $ q $ -ramsey。此外，如果另外没有适当的子图$ g'$ g $ of $ g $是$ q $ -ramsey，则据说$ h $的$ g $是最小的$ q $ -ramsey。 1976年，Burr，Erdős和Lovász启动了参数$ S_Q（H）$的研究，该参数定义为所有最小$ Q $ -Ramsey图形中最小的最小学位。在本文中，我们考虑了确定$ h $的最小值$ s_q（h）$ a a a $ q $ -ramsey图的问题的问题。具体来说，我们试图识别最小值$ q $ -ramsey图可以包含许多此类顶点的图形。我们称之为满足此属性$ s_q $的图形。除其他结果外，我们证明，对于任何整数$ q \ geq 2 $，每个周期都是$ s_q $的。我们还讨论了$ h $是一个具有吊坠边缘的集团或集团的案例，从而扩大了Burr等人的先前结果。和Fox等。为了证明我们的结果并构造了合适的最小拉姆西图，我们开发了某些新的小工具图，称为模式小工具，这些图形概括和扩展了早期的构造，这些结构已被证明在研究最小Ramsey图的研究中很有用。这些新小工具可能具有独立的兴趣。
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$. Further, 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 $s_q(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 $s_q(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 $s_q$-abundant. Among other results, we prove that every cycle is $s_q$-abundant for any integer $q\geq 2$. We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr et al. and Fox et al. To prove our results and construct suitable minimal Ramsey graphs, we develop certain new gadget graphs, called pattern gadgets, which generalize and extend earlier constructions that have proven useful in the study of minimal Ramsey graphs. These new gadgets might be of independent interest.
