Star-critical Ramsey numbers and regular Ramsey numbers for stars

Abstract

Let $G$ be a graph, $H$ be a subgraph of $G$, and let $G-H$ be the graph obtained from $G$ by removing a copy of $H$. Let $K_{1,n}$ be the star on $n+1$ vertices. Let $t\ge 2$ be an integer and $H_1,\dots ,H_t$ and $H$ be graphs, and let $H\to (H_1,\dots ,H_t)$ denote that every $t$ coloring of $E(H)$ yields a monochromatic copy of $H_i$ in color $i$ for some $i\in [t]$. Ramsey number $r(H_1,\dots ,H_t)$ is the minimum integer $N$ such that $K_N\to (H_1,\dots ,H_t)$. Star-critical Ramsey number $r_{\ast }(H_1,\dots ,H_t)$ is the minimum integer $k$ such that $K_N-K_{1,N-1-k}\to (H_1,\dots ,H_t)$ where $N=r(H_1,\dots ,H_t)$. Let $rr(H_1,\dots ,H_t)$ be the regular Ramsey number for $H_1,\dots ,H_t$, which is the minimum integer $r$ such that if $G$ is an $r$-regular graph on $r(H_1,\dots ,H_t)$ vertices, then $G\to (H_1,\dots ,H_t)$. Let $m_1,\dots ,m_t$ be integers larger than one, exactly $k$ of which are even. In this paper, we prove that if $k\ge 2$ is even, then $r_{\ast }(K_{1,m_1},\dots ,K_{1,m_t})={\sum }_{i=1}^t{m}_i-t+1-\frac{k}{2}$ which disproves a conjecture of Budden and DeJonge in 2022. Furthermore, we prove that if $k\ge 2$ is even, then $rr(K_{1,m_1},\dots ,K_{1,m_t})={\sum }_{i=1}^t{m}_i-t$. Otherwise, $rr(K_{1,m_1},\dots ,K_{1,m_t})={\sum }_{i=1}^t{m}_i-t+1$.