---

Discontinuity, Nonlinearity, and Complexity 11(2) (2022) 243--251 | DOI:10.5890/DNC.2022.06.005

Xueli Su, Yan Liu

\small School of Mathematical Sciences, South China Normal University, Guangzhou, 510631, P.R. China

Download Full Text PDF

 

Abstract

A Gallai $k$-coloring is a $k$-edge coloring of a complete graph in which there are no rainbow triangles. For two given graphs $H, G$ and two positive integers $k,s$ with $s\leq k$, the $k$-colored Gallai-Ramsey number $gr_{k}(K_{3}: s\cdot H,~ (k-s)\cdot G)$ is the minimum integer $n$ such that every Gallai $k$-colored $K_{n}$ contains a monochromatic copy of $H$ colored by one of the first $s$ colors or a monochromatic copy of $G$ colored by one of the remaining $k-s$ colors. In this paper, we determine the value of Gallai-Ramsey number in the case that $H=K_{4}^{+}$ and $G=K_{3}$. Thus the Gallai-Ramsey number $gr_{k}(K_{3}: K_{4}^{+})$ is obtained.

Acknowledgments

This work is supported by the Science and Technology Program of Guangzhou, China(No.202002030183), the Natural Science Foundation of Guangdong, China (No.2021A1515012045), the Natural Science Foundation of Qinghai, China (No. 2020-ZJ-924), and by the National Natural Science Foundation of China (No.12161073).

References

1. [1]	Erd\H{o}s, P., Faudree, R., Rousseau, C., and Schelp, R. (1978), The size Ramsey number, Period. Math. Hungar., 9(1-2), 145-161.

2. [2]	Faudree, R. and Schelp, R. (2002), A survey of results on the size Ramsey number, in: Paul Erd\H{os and his mathematics, II (Budapest, 1999), in: Bolyai Soc. Math. Stud.}, 11, J{a}nos Bolyai Math. Soc., Budapest, 291-309.

3. [3]	Graham, R., Rothschild, B., and Spencer, J. (1990), Ramsey Theory, { Wiley, New York}.

4. [4]	Radziszowski, S.P. (1996), Small Ramsey Numbers, Electronic J. Combin., 1.

5. [5]	K\"{o}rner, J. and Simonyi, G. (2000), Graph pairs and their entropies: modularity problems, Combinatorica, 20, 227-240.

6. [6]	Gallai, T. (1967), Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., 18, 25-66.

7. [7]	Gy{a}rf{a}s, A. and Simonyi, G. (2004), Edge colorings of complete graphs without tricolored triangles, J. Graph Theory, 46(3), 211-216.

8. [8]	Cameron, K., Edmonds, J., and Lov{a}sz, L. (1986), A note on perfect graphs, Period. Math. Hungar., 17, 173-175.

9. [9]	Fox, J., Grinshpun, A., and Pach, J. (2015), The Erd\H{o}s-Hajnal conjecture for rainbow triangles, J. Combin. Theory Ser. B, 111, 75-125.

10. [10]	Fujita, S., Magnant, C., and Ozeki, K. (2010), Rainbow generalizations of Ramsey theory: a survey, Graphs and Combin., 26, 1-30.

11. [11]	Liu, H., Magnant, C., Saito, A., Schiermeyer, I., and Shi, Y. (2019), Gallai-ramsey number for $K_{4}$, J. Graph Theory, 1-14.

12. [12]	Wu, H. and Magnant, C. (2018), Gallai-Ramsey numbers for monochromatic trangles or 4-cycles, Graphs Combin., 34, 1315-1324.

13. [13]	Chung, F.R.K. and Graham, R.L. (1983), Edge-colored complete graphs with precisely colored subgraphs, Combinatorica, 3, 315-324.

14. [14]	Gy{a}rf{a}s, A., S{a}rk\"{o}zy, G., Seb\"{o}, A., and Selkow, S. (2010), Ramsey-type results for Gallai-colorings, J. Graph Theory, 64, 233-243.

15. [15]	Cameron, K. and Edmonds, J. (1997), Lambda composition, J. Graph Theory, 26(1), 9-16.

16. [16]	Clancy, M. (1977), Some Small Ramsey Numbers, J. Graph Theory, 89-91.

17. [17]	Harborth, H. and Mengersen, I. (1988), All Ramsey number for five vertices and seven or eight edges, Discrete Math., 91-98.