All Ramsey critical graphs for a large tree versus $tK_{m}$
All Ramsey critical graphs for a large tree versus $tK_{m}$
Let $H, H_{1}$ and $H_{2}$ be graphs, and let $H\rightarrow (H_{1}, H_{2})$ denote that any red-blue coloring of $E(H)$ yields a red copy of $H_{1}$ or a blue copy of $H_{2}$. The Ramsey number for $H_{1}$ versus $H_{2}$, $r(H_{1}, H_{2})$, is the minimum integer $N$ such that $K_{N}\rightarrow (H_{1}, H_{2})$. The Ramsey critical graph $H$ for $H_{1}$ versus $H_{2}$ is a red-blue edge-colored $K_{N- 1}$ such that $H\not\rightarrow (H_{1}, H_{2})$, where $N= r(H_{1}, H_{2})$. In this paper, we characterize all Ramsey critical graphs for a large tree versus $tK_{m}$. As a corollary, we determine the star-critical Ramsey number for a large tree versus $tK_{m}$.
Zhiyu Cheng、Zhidan Luo、Pingge Chen
数学
Zhiyu Cheng,Zhidan Luo,Pingge Chen.All Ramsey critical graphs for a large tree versus $tK_{m}$[EB/OL].(2025-06-23)[2025-07-02].https://arxiv.org/abs/2506.18235.点此复制
评论