Geodesic
Gallai-Ramsey Numbers for Rainbow $S_3^+$ and Monochromatic Paths
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 349-362.

Voir la notice de l'article provenant de la source Library of Science

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 ≥ 5), gr_k(S_3^+ : mP_2) = (m-1)k+m+1 (k ≥ 1), gr_k(S_3^+ : P_3 ∪ P_2) = k+4 (k ≥ 5) and gr_k( S_3^+ : 2P_3) = k+5 (k ≥1).
Keywords: Gallai-Ramsey number, rainbow coloring, monochromatic paths 
@article{DMGT_2022_42_2_a2,
     author = {Li, Xihe and Wang, Ligong},
     title = {Gallai-Ramsey {Numbers} for {Rainbow} $S_3^+$  and {Monochromatic} {Paths}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {349--362},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a2/}
}
TY  - JOUR
AU  - Li, Xihe
AU  - Wang, Ligong
TI  - Gallai-Ramsey Numbers for Rainbow $S_3^+$  and Monochromatic Paths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 349
EP  - 362
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a2/
LA  - en
ID  - DMGT_2022_42_2_a2
ER  - 
%0 Journal Article
%A Li, Xihe
%A Wang, Ligong
%T Gallai-Ramsey Numbers for Rainbow $S_3^+$  and Monochromatic Paths
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 349-362
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a2/
%G en
%F DMGT_2022_42_2_a2
Li, Xihe; Wang, Ligong. Gallai-Ramsey Numbers for Rainbow $S_3^+$  and Monochromatic Paths. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 349-362. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a2/

[1] D. Bruce and Z.-X. Song, Gallai-Ramsey numbers of C7 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 K3-free and S3+-free colorings (2019), submitted.

[19] H. Liu, C. Magnant, A. Saito, I. Schiermeyer and Y.T. Shi, Gallai-Ramsey number for K4, J. Graph Theory (2019), in-press. https://doi.org/10.1002/jgt.22514

[20] C. Magnant and I. Schiermeyer, Gallai-Ramsey number for K5 (2019). arXiv:1901.03622

[21] M.W. Scobee, On the Ramsey number R(m1P3, m2P3, m3P3) 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.