Article in volume
Authors:
Title:
Star-critical Ramsey numbers and regular Ramsey numbers for stars
PDFSource:
Discussiones Mathematicae Graph Theory 45(2) (2025) 755-762
Received: 2023-12-29 , Revised: 2024-06-15 , Accepted: 2024-06-15 , Available online: 2024-06-27 , https://doi.org/10.7151/dmgt.2550
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\geq 2$ be an integer and $H_{1}, \dots, H_{t}$ and $H$
be graphs, and let $H\rightarrow (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]$. The Ramsey number $r(H_{1}, \dots, H_{t})$ is the minimum integer
$N$ such that $K_{N}\rightarrow (H_{1}, \dots, H_{t})$. The star-critical Ramsey
number $r_{*}(H_{1}, \dots, H_{t})$ is the minimum integer $k$ such that
$K_{N}- K_{1, N- 1- k}\rightarrow (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\rightarrow
(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\geq 2$ is
even, then $r_{*}(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
$$
rr(K_{1, m_{1}}, \dots, K_{1, m_{t}})= \begin{cases}
\sum_{i= 1}^{t} m_{i}- t, & \text{$k\geq 2$ is even},\\
\sum_{i= 1}^{t} m_{i}- t+ 1, & otherwise.
\end{cases}
$$
Keywords:
star-critical Ramsey numbers, regular Ramsey numbers, stars
References:
- B. Bollobás, Extremal Graph Theory, Reprint of the 1978 original (Dover Publications, Inc., Mineola, New York, 2004).
- M.R. Budden and E. DeJonge, Multicolor star-critical Ramsey numbers and Ramsey-good graphs, Electron. J. Graph Theory Appl. EJGTA 10 (2022) 51–66.
https://doi.org/10.5614/ejgta.2022.10.1.4 - S. Burr and J. Roberts, On Ramsey numbers for stars, Util. Math. 4 (1973) 217–220.
- F. Harary, Graph Theory (Addison-Wesley Publishing Company, Inc., New York, 1969).
- F. Harary, Recent results on generalized Ramsey theory for graphs, in: Graph Theory and Applications, Y. Alavi, D.R. Lick and A.T. White (Ed(s)), Lecture Notes in Math. 303, (Springer, Berlin, Heidelberg, 1972) 125–138.
https://doi.org/10.1007/BFb0067364 - J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math. 159 (2011) 328–334.
https://doi.org/10.1016/j.dam.2010.11.007 - E. Lucas, Récréations Mathématiques, vol. 2 (Gautheir–Villars, Paris, 1892).
- R.H. Schelp, Some Ramsey-Turán type problems and related questions, Discrete Math. 312 (2012) 2158–2161.
https://doi.org/10.1016/j.disc.2011.09.015
Close