Article in volume
Authors:
Title:
On the Ramsey numbers of non-star trees versus connected graphs of order six
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 331-349
Received: 2019-06-22 , Revised: 2020-09-27 , Accepted: 2020-09-28 , Available online: 2020-11-02 , https://doi.org/10.7151/dmgt.2370
Abstract:
This paper completes our studies on the Ramsey number $r(T_n,G)$ for trees
$T_n$ of order $n$ and connected graphs $G$ of order six. If $\chi(G) \ge 4$,
then the values of $r(T_n,G)$ are already known for any tree $T_n$. Moreover,
$r(S_n,G)$, where $S_n$ denotes the star of order $n$, has been investigated in
case of $\chi(G) \le 3$. If $\chi(G) = 3$ and $G \neq K_{2,2,2}$, then
$r(S_n,G)$ has been determined except for some $G$ and some small $n$. Partial
results have been obtained for $r(S_n,K_{2,2,2})$ and for $r(S_n,G)$ with
$\chi(G) = 2$. In the present paper we investigate $r(T_n,G)$ for non-star
trees $T_n$ and $\chi(G) \le 3$. Especially, $r(T_n,G)$ is completely evaluated
for any non-star tree $T_n$ if $\chi(G) = 3$ where $G \neq K_{2,2,2}$, and
$r(T_n,K_{2,2,2})$ is determined for a class of trees $T_n$ with small maximum
degree. In case of $\chi(G) = 2$, $r(T_n,G)$ is investigated for $T_n = P_n$,
the path of order $n$, and for $T_n= B_{2,n-2}$, the special broom of order $n$
obtained by identifying the centre of a star $S_3$ with an end-vertex of a path
$P_{n-2}$. Furthermore, the values of $r(B_{2,n-2},S_{m})$ are determined for
all $n$ and $m$ with $n \ge m - 1$. As a consequence of this paper, $r(F,G)$ is
known for all trees $F$ of order at most five and all connected graphs $G$ of
order at most six.
Keywords:
Ramsey number, Ramsey goodness, tree, star, path, broom, small graph
References:
- S.A. Burr, P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, Some complete bipartite graph-tree Ramsey numbers, Ann. Discrete Math. 41 (1989) 79–89.
https://doi.org/10.1016/S0167-5060(08)70452-7 - G. Chartrand, R.J. Gould and A.D. Polimeni, On Ramsey numbers of forests versus nearly complete graphs, J. Graph Theory 4 (1980) 233–239.
https://doi.org/10.1002/jgt.3190040211 - V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977) 93.
https://doi.org/10.1002/jgt.3190010118 - V. Chvátal and F. Harary, Generalized Ramsey theory for graphs III: Small off-diagonal numbers, Pacific J. Math. 41 (1972) 335–345.
https://doi.org/10.2140/pjm.1972.41.335 - M. Clancy, Some small Ramsey numbers, J. Graph Theory 1 (1977) 89–91.
https://doi.org/10.1002/jgt.3190010117 - P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, The book-tree Ramsey numbers, Scientia, Ser. A: Math. Sci. 1 (1988) 111–117.
- R.J. Faudree, C.C. Rousseau and R.H. Schelp, Small order graph-tree Ramsey numbers, Discrete Math. 72 (1988) 119–127.
https://doi.org/10.1016/0012-365X(88)90200-2 - R.J. Gould and M.S. Jacobson, On the Ramsey number of trees versus graphs with large clique number, J. Graph Theory 7 (1983) 71–78.
https://doi.org/10.1002/jgt.3190070109 - Y.B. Guo and L. Volkmann, Tree-Ramsey numbers, Australas. J. Combin. 11 (1995) 169–175.
- F. Harary, Recent results on generalized Ramsey theory for graphs, in: Graph Theory and Applications, Lecture Notes in Mathematics Vol. 303, Y. Alavi et al. (Ed(s)), (Springer, Berlin 1972) 125–138.
- R. Lortz and I. Mengersen, On the Ransey numbers for stars versus connected graphs of order six, Australas. J. Combin. 73 (2019) 1–24.
- R. Lortz and I. Mengersen, On the Ramsey numbers $r(S_n,K_6-3K_2)$, J. Combin. Math. Combin. Comput., to appear.
- R. Lortz and I. Mengersen, All missing Ramsey numbers for trees versus the four-page book, submitted.
- T.D. Parsons, Path-star Ramsey numbers, J. Combin. Theory Ser. B 17 (1974) 51–58.
https://doi.org/10.1016/0095-8956(74)90048-3 - T.D. Parsons, Ramsey graphs and block designs I, Trans. Amer. Math. Soc. 209 (1975) 33–44.
https://doi.org/10.1090/S0002-9947-1975-0396317-X - A. Pokrovskiy and B. Sudakov, Ramsey goodness of paths, J. Combin. Theory Ser. B 122 (2017) 384–390.
https://doi.org/10.1016/j.jctb.2016.06.009 - S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2017) #DS1.15.
https://doi.org/10.37236/21 - C.C. Rousseau and J. Sheehan, A class of Ramsey problems involving trees, J. Lond. Math. Soc. (2) 18 (1978) 392–396.
https://doi.org/10.1112/jlms/s2-18.3.392 - Y. Wu, Y. Sun, R. Zhang and S.P. Radziszowski, Ramsey numbers of $C_4$ versus wheels and stars, Graphs Combin. 31 (2015) 2437–2446.
https://doi.org/10.1007/s00373-014-1504-3
Close