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:

X.H. Li

Xihe Li

School of Mathematics and Statistics,
Northwestern Polytechnical University, Xi'an, Shaanxi 710129, P.R. China.
Xi'an-Budapest Joint Research Center for Combinatorics,
Northwestern Polytechnical University, Xi'an, Shaanxi 710129, P. R. China

email: lxhdhr@163.com

L.G. Wang

Ligong Wang

School of Mathematics and Statistics,
Northwestern Polytechnical University, Xi'an, Shaanxi 710129, P.R. China.
Xi'an-Budapest Joint Research Center for Combinatorics,
Northwestern Polytechnical University, Xi'an, Shaanxi 710129, P. R. China

email: lgwangmath@163.com

0000-0002-6160-1761

Title:

Gallai-Ramsey numbers for rainbow $S^{+}_{3}$ and monochromatic paths

PDF

Source:

Discussiones Mathematicae Graph Theory 42(2) (2022) 349-362

Received: 2018-06-13 , Revised: 2019-03-18 , Accepted: 2019-10-22 , Available online: 2020-03-04 , https://doi.org/10.7151/dmgt.2310

Abstract:

Motivated by Ramsey theory and other rainbow-coloring-related problems, we consider edge-colorings of complete graphs without rainbow copy of some fixed subgraphs. Given two graphs $G$ and $H$, the $k$-colored Gallai-Ramsey number $gr_k(G : H)$ is defined to be the minimum positive integer $n$ such that every $k$-coloring of the complete graph on $n$ vertices contains either a rainbow copy of $G$ or a monochromatic copy of $H$. Let $S^{+}_{3}$ be the graph on four vertices consisting of a triangle with a pendant edge. In this paper, we prove that $gr_k(S^{+}_{3} : P_5)=k+4$ ($k\geq 5$), $gr_k(S^{+}_{3} : mP_2)= (m-1)k+m+1$ ($k\geq 1$), $gr_k(S^{+}_{3} : P_3 \cup P_2)= k+4$ ($k\geq 5$) and $gr_k(S^{+}_{3} : 2P_3)=k+5$ ($k\geq 1$).

Keywords:

Gallai-Ramsey number, rainbow coloring, monochromatic paths

References:

  1. D. Bruce and Z.-X. Song, Gallai-Ramsey numbers of $C_7$ with multiple colors, Discrete Math. 342 (2019) 1191–1194.
    https://doi.org/10.1016/j.disc.2019.01.003
  2. S.A. Burr, P. Erdős and J.H. Spencer, Ramsey theorems for multiple copies of graphs, Trans. Amer. Math. Soc. 209 (1975) 87–99.
    https://doi.org/10.1090/S0002-9947-1975-0409255-0
  3. F.R.K. Chung and R. Graham, Edge-colored complete graphs with precisely colored subgraphs, Combinatorica 3–4 (1983) 315–324.
    https://doi.org/10.1007/BF02579187
  4. E.J. Cockayne and P.J. Lorimer, The Ramsey number for stripes, J. Aust. Math. Soc. 19 (1975) 252–256.
    https://doi.org/10.1017/S1446788700029554
  5. R.J. Faudree, R. Gould, M. Jacobson and C. Magnant, Ramsey numbers in rainbow triangle free colorings, Australas. J. Combin. 46 (2010) 269–284.
  6. R.J. Faudree and R.H. Schelp, Path-path Ramsey-type numbers for the complete bipartite graph, J. Combin. Theory Ser. B 19 (1975) 161–173.
    https://doi.org/10.1016/0095-8956(75)90081-7
  7. J. Fox, A. Grinshpun and J. Pach, The Erdős-Hajnal conjecture for rainbow triangles, J. Combin. Theory Ser. B 111 (2015) 75–125.
    https://doi.org/10.1016/j.jctb.2014.09.005
  8. S. Fujita and C. Magnant, Gallai-Ramsey numbers for cycles, Discrete Math. 311 (2011) 1247–1254.
    https://doi.org/10.1016/j.disc.2009.11.004
  9. S. Fujita and C. Magnant, Extensions of Gallai-Ramsey results, J. Graph Theory 70 (2012) 404–426.
    https://doi.org/10.1002/jgt.20622
  10. S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizations of Ramsey theory: A survey, Graphs Combin. 26 (2010) 1–30.
    https://doi.org/10.1007/s00373-010-0891-3
  11. S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizations of Ramsey theory: A dynamic survey, Theory Appl. Graphs 0(1) (2014) Article 1.
    https://doi.org/10.20429/tag.2014.000101
  12. T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66.
    https://doi.org/10.1007/BF02020961
  13. L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 (1967) 167–170.
    https://doi.org/10.1007/BF01350150
  14. J. Gregory, Gallai-Ramsey Number of an $8$-Cycle, Electronic Theses and Dissertations (Georgia Southern University, 2016).
  15. A. Gyárfás and G.N. Sárközy, A. Sebő and S. Selkow, Ramsey-type results for Gallai colorings, J. Graph Theory 64 (2010) 233–243.
    https://doi.org/10.1002/jgt.20452
  16. A. Gyárfás and G. Simonyi, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46 (2004) 211–216.
    https://doi.org/10.1002/jgt.20001
  17. M. Hall, C. Magnant, K. Ozeki and M. Tsugaki, Improved upper bounds for Gallai–Ramsey numbers of paths and cycles, J. Graph Theory 75 (2014) 59–74.
    https://doi.org/10.1002/jgt.21723
  18. X.H. Li and L.G. Wang, Monochromatic stars in rainbow $K_3$-free and $S^{+}_{3}$-free colorings (2019), submitted.
  19. H. Liu, C. Magnant, A. Saito, I. Schiermeyer and Y.T. Shi, Gallai-Ramsey number for $K_4$, J. Graph Theory(2019), in press.
    https://doi.org/10.1002/jgt.22514
  20. C. Magnant and I. Schiermeyer, Gallai-Ramsey number for $K_5$ (2019).
    arXiv: 1901.03622
  21. M.W. Scobee, On the Ramsey number $R(m_1P_3, m_2P_3, m_3P_3)$ and related results, a survey of classical and generalized Ramsey theory with a presentation of the three color Ramsey number for multiple copies of the path on three vertices, MA Thesis (University of Louisville, 1993).
  22. Y.S. Yang and P. Rowlinson, On the third Ramsey numbers of graphs with five edges, J. Combin. Math. Combin. Comput. 11 (1992) 213–222.
Close