DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

R. Lortz

Roland Lortz

Technische Universität Braunschweig, Institut für Analysis und Algebra, AG Algebra, 38092 Braunschweig

email: r.lortz@tu-braunschweig.de

I. Mengersen

Ingrid Mengersen

Retired, formerly: Ostfalia University of Applied Sciences, Department of Computer Science, Wolfenbüttel, Germany

email: ingrid.mengersen@t-online.de

Title:

On the Ramsey numbers of non-star trees versus connected graphs of order six

PDF

Source:

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:

  1. 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
  2. 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
  3. V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977) 93.
    https://doi.org/10.1002/jgt.3190010118
  4. 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
  5. M. Clancy, Some small Ramsey numbers, J. Graph Theory 1 (1977) 89–91.
    https://doi.org/10.1002/jgt.3190010117
  6. 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.
  7. 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
  8. 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
  9. Y.B. Guo and L. Volkmann, Tree-Ramsey numbers, Australas. J. Combin. 11 (1995) 169–175.
  10. 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.
  11. R. Lortz and I. Mengersen, On the Ransey numbers for stars versus connected graphs of order six, Australas. J. Combin. 73 (2019) 1–24.
  12. R. Lortz and I. Mengersen, On the Ramsey numbers $r(S_n,K_6-3K_2)$, J. Combin. Math. Combin. Comput., to appear.
  13. R. Lortz and I. Mengersen, All missing Ramsey numbers for trees versus the four-page book, submitted.
  14. 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
  15. 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
  16. 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
  17. S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2017) #DS1.15.
    https://doi.org/10.37236/21
  18. 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
  19. 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