论文标题
双星的多色拉姆齐号
Multicolor Ramsey Number for Double Stars
论文作者
论文摘要
对于图$ h $和整数$ k \ ge1 $，让$ r（h; k）$和$ r_ \ ell（h; k）$表示$ k $ -color-color-color ramsey编号和列表$ h $的ramsey号码。受到阿隆，布西奇，卡尔瓦里，库珀瓦瑟和szabó的工作的激励，他们启动了列表列表拉姆齐的图形和超图的系统研究，并猜想$ r（k_ {1，n}; k）$ r_ \ el ell（k_ r_ el y y y y ye $ ksse asse ys $ ksse ys $ $ s（n，m）$，其中$ n \ ge m \ ge1 $。据我们所知，在$ r（s（n，m）; k）$ $ k \ ge3 $的确切值中，几乎没有知名度。 1975年的Erdős和Graham的经典结果断言，每棵树$ t $ a $ n \ ge 1 $边缘和$ k $足够大，以至于$ n $ n $ divide $ k-1 $。使用在设定系统中的民间传说双计数论点和完整图的边缘色数，我们证明，如果$ k $是奇怪的，而$ n $与$ m $和$ k $相比，则足够大，那么\ [s（n，m）= kn+m+2。总是相等的，它保持开放。我们还证明$ r（s^m_n; k）= k（n-1）+m+2 $如果$ k $是奇数的，而$ n $与$ m $和$ k $相比，$ 1 \ le m \ le m \ le m \ le n $和$ s^m_n $可从$ k_ {1，n} $中获得，每$ k_ {1，n} $由$ m $ m $ m $ edges获得。我们以$ s（n，m）$和$ s^m_n $的列表列表的一些观察结束了论文。
For a graph $H$ and integer $k\ge1$, let $r(H;k)$ and $r_\ell(H;k)$ denote the $k$-color Ramsey number and list Ramsey number of $H$, respectively. Motivated by the work of Alon, Bucić, Kalvari, Kuperwasser and Szabó, who initiated the systematic study of list Ramsey numbers of graphs and hypergraphs, and conjectured that $ r(K_{1,n};k)$ and $r_\ell(K_{1,n};k)$ are always equal, we study the $k$-color Ramsey number for double stars $S(n,m)$, where $n\ge m\ge1$. To the best of our knowledge, little is known on the exact value of $r(S(n,m);k)$ when $k\ge3$. A classic result of Erdős and Graham from 1975 asserts that $r(T;k)>k(n-1)+1$ for every tree $T$ with $n\ge 1$ edges and $k$ sufficiently large such that $n$ divides $k-1$. Using a folklore double counting argument in set system and the edge chromatic number of complete graphs, we prove that if $k$ is odd and $n$ is sufficiently large compared with $m$ and $k$, then \[ r(S(n,m);k)=kn+m+2.\] This is a step in our effort to determine whether $r(S(n,m);k)$ and $r_\ell(S(n,m);k)$ are always equal, which remains wide open. We also prove that $ r(S^m_n;k)=k(n-1)+m+2$ if $k $ is odd and $n$ is sufficiently large compared with $m$ and $k$, where $1\le m\le n$ and $S^m_n$ is obtained from $K_{1, n}$ by subdividing $m$ edges each exactly once. We end the paper with some observations towards the list Ramsey number for $S(n,m)$ and $S^m_n$.
