On Bounded Degree Graphs with Large Size-Ramsey Numbers
On Bounded Degree Graphs with Large Size-Ramsey Numbers
复制标题
DOI：
10.1007/s00493-023-00056-1
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
K. Tikhomirov
中科院分区：
文献类型：
--
作者：
K. Tikhomirov
图的大小Ramsey数定义为最小的整数，使得存在一个图G，其边的每一个2-着色都包含一个的单色拷贝。Rödl和Szemerédi通过讨论Beck的一个问题，证明了对于任意的图，存在n个顶点，每个顶点的度至多为3，对于一个普适常数，其大小Ramsey数至少为3。在本说明中，我们表明，修改Rödl和Szemerédi的建设导致一个界限。
The size-Ramsey numberof a graphis defined as the smallest integermso that there exists a graphGwithmedges such that every 2–coloring of the edges ofGcontains a monochromatic copy of. Answering a question of Beck, Rödl and Szemerédi showed that for everythere exists a graphonnvertices each of degree at most three, with size-Ramsey number at leastfor a universal constant. In this note we show that a modification of Rödl and Szemerédi’s construction leads to a bound.