Multicolor Ramsey and list Ramsey numbers for star-like trees

Source abstract

For a graph $H$, the $k$-color Ramsey number $r(H;k)$ is the least integer $N$ such that every $k$-edge-coloring of $K_N$ contains a monochromatic copy of $H$. A $k$-list assignment has $|L(e)|=k$ for every edge. The list Ramsey number $r_\ell(H;k)$ is the least integer $N$ for which there exists a $k$-list assignment on $E(K_N)$ such that every coloring from the lists contains a monochromatic copy of $H$. Let $K_{1,n}$ be a star, $S(n,m)$ the double star obtained by joining the centers of $K_{1,n}$ and $K_{1,m}$, and $S_n^m$ the graph obtained from $K_{1,n}$ by subdividing $m$ edges once. Alon et al.\ conjectured that $r_\ell(K_{1,n};k)=r(K_{1,n};k)$ for all $k,n\ge1$. In this paper, we confirm their conjecture for all $k\ge1$ and $n\ge3$ by a unified direct proof. For even $k\ge4$ and under explicit parameter conditions, we prove that $r(S(n,m);k)=kn+m+2$ for even $n$ and $r(S_n^m;k)=k(n-1)+m+2$ for odd $n$. For two colors, we establish a general list Ramsey lower bound and determine the common values of Ramsey and list Ramsey numbers for double and subdivided stars in explicit parameter ranges. These results close several gaps in the known bounds.