Gallai-Ramsey Numbers for Monochromatic $K_4^{+}$ or $K_{3}$
DOI:
https://doi.org/10.5890/DNC.2022.06.005Abstract
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.References
[1] ErdH{o}s, P., Faudree, R., Rousseau, C., and Schelp, R. (1978), The size Ramsey number, Period. Math. Hungar., 9(1-2), 145-161.
[2] Faudree, R. and Schelp, R. (2002), A survey of results on the size Ramsey number, in: Paul ErdH{os and his mathematics, II (Budapest, 1999), in: Bolyai Soc. Math. Stud.}, 11, J{a}nos Bolyai Math. Soc., Budapest, 291-309.
[3] Graham, R., Rothschild, B., and Spencer, J. (1990), Ramsey Theory, { Wiley, New York}.
[4] Radziszowski, S.P. (1996), Small Ramsey Numbers, Electronic J. Combin., 1.
[5] K"{o}rner, J. and Simonyi, G. (2000), Graph pairs and their entropies: modularity problems, Combinatorica, 20, 227-240.
[6] Gallai, T. (1967), Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., 18, 25-66.
[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] Cameron, K., Edmonds, J., and Lov{a}sz, L. (1986), A note on perfect graphs, Period. Math. Hungar., 17, 173-175.
[9] Fox, J., Grinshpun, A., and Pach, J. (2015), The ErdH{o}s-Hajnal conjecture for rainbow triangles, J. Combin. Theory Ser. B, 111, 75-125.
[10] Fujita, S., Magnant, C., and Ozeki, K. (2010), Rainbow generalizations of Ramsey theory: a survey, Graphs and Combin., 26, 1-30.
[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] Wu, H. and Magnant, C. (2018), Gallai-Ramsey numbers for monochromatic trangles or 4-cycles, Graphs Combin., 34, 1315-1324.
[13] Chung, F.R.K. and Graham, R.L. (1983), Edge-colored complete graphs with precisely colored subgraphs, Combinatorica, 3, 315-324.
[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] Cameron, K. and Edmonds, J. (1997), Lambda composition, J. Graph Theory, 26(1), 9-16.
[16] Clancy, M. (1977), Some Small Ramsey Numbers, J. Graph Theory, 89-91.
[17] Harborth, H. and Mengersen, I. (1988), All Ramsey number for five vertices and seven or eight edges, Discrete Math., 91-98.
Article Metrics
Usage tracking begins September 1, 2026.