Skip Navigation Links
Discontinuity, Nonlinearity, and Complexity

Dimitry Volchenkov (editor), Dumitru Baleanu (editor)

Dimitry Volchenkov(editor)

Mathematics & Statistics, Texas Tech University, 1108 Memorial Circle, Lubbock, TX 79409, USA


Dumitru Baleanu (editor)

Cankaya University, Ankara, Turkey; Institute of Space Sciences, Magurele-Bucharest, Romania


Gallai-Ramsey Numbers for Monochromatic $K_4^{+}$ or $K_{3}$

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



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.


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).


  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.