The vertex size-Ramsey number

详细信息    查看全文

• 作者：Andrzej Dudek ; ^{andrzej.dudek@wmich.edu" class="auth_mail" title="E-mail the corresponding author} ; Linda Lesniak ^{linda.lesniak@wmich.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Ramsey numbers ; Vertex colorings
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 June 2016
• 年：2016
• 卷：339
• 期：6
• 页码：1753-1762
• 全文大小：397 K

文摘

In this paper, we study an analogue of size-Ramsey numbers for vertex colorings. For a given number of colors r$r$ and a graph G$G$ the vertex size-Ramsey number of G$G$, denoted by ${\hat{R}}_v(G,r)$, is the least number of edges in a graph H$H$ with the property that any r$r$-coloring of the vertices of H$H$ yields a monochromatic copy of G$G$. We observe that ${\Omega }_r\left(\Delta n\right)={\hat{R}}_v(G,r)=O_r\left(n^2\right)$ for any G$G$ of order n$n$ and maximum degree Δ$\Delta$, and prove that for some graphs these bounds are tight. On the other hand, we show that even 3-regular graphs can have nonlinear vertex size-Ramsey numbers. Finally, we prove that ${\hat{R}}_v(T,r)=O_r\left({\Delta }^{2}n\right)$ for any tree of order n$n$ and maximum degree Δ$\Delta$, which is only off by a factor of Δ$\Delta$ from the best possible.