Bruce, Dylan; Song, Zi-Xia Gallai-Ramsey numbers of \(C_7\) with multiple colors. (English) Zbl 1405.05054 Discrete Math. 342, No. 4, 1191-1194 (2019). Summary: We study Ramsey-type problems in Gallai-colorings. Given a graph \(H\) and an integer \(k \geq 1\), the Gallai-Ramsey number \(\operatorname{GR}_k(H)\) is the least positive integer \(n\) such that every \(k\)-coloring of the edges of the complete graph on \(n\) vertices contains either a rainbow triangle or a monochromatic copy of \(H\). It turns out that \(\operatorname{GR}_k(H)\) behaves more nicely than the classic Ramsey number \(\operatorname{R}_k(H)\). However, finding exact values of \(\operatorname{GR}_k(H)\) is far from trivial. In this paper, we prove that \(\operatorname{GR}_k(C_7) = 3 \cdot 2^k + 1\) for all \(k \geq 1\). Our technique relies heavily on the structural result of Gallai on edge-colorings of complete graphs without rainbow triangles. Cited in 9 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05D10 Ramsey theory Keywords:Gallai-coloring; Gallai-Ramsey number; rainbow triangle PDFBibTeX XMLCite \textit{D. Bruce} and \textit{Z.-X. Song}, Discrete Math. 342, No. 4, 1191--1194 (2019; Zbl 1405.05054) Full Text: DOI References: [1] Bondy, J. A.; Erdős, P., Ramsey numbers for cycles in graphs, J. Combin. Theory Ser. B, 14, 46-54 (1973) · Zbl 0248.05127 [2] Bosse, C.; Song, Z.-X., Multicolor Gallai-Ramsey numbers of \(C_9\) and \(C_{11} (2018)\), submitted for publication [3] Bosse, C.; Song, Z.-X.; Zhang, J., Improved upper bounds for Gallai-Ramsey numbers of odd cycles (2018), submitted for publication [4] Cameron, K.; Edmonds, J.; Lovász, L., A note on perfect graphs, Period. Math. Hungar., 17, 173-175 (1986) · Zbl 0605.05014 [5] Chung, F. R.K.; Graham, R., Edge-colored complete graphs with precisely colored subgraphs, Combinatorica, 3, 315-324 (1983) · Zbl 0529.05041 [6] Faudree, R. J.; Schelten, A.; Schiermeyer, I., The Ramsey Number \(r(C_7, C_7, C_7)\), Discuss. Math. Graph Theory, 23, 141-158 (2003) · Zbl 1049.05055 [7] Fox, J.; Grinshpun, A.; Pach, J., The Erdős-Hajnal conjecture for rainbow triangles, J. Combin. Theory Ser. B, 111, 75-125 (2015) · Zbl 1307.05069 [8] Fujita, S.; Magnant, C., Gallai-Ramsey numbers for cycles, Discrete Math., 311, 1247-1254 (2011) · Zbl 1222.05186 [9] Fujita, S.; Magnant, C.; Ozeki, K., Rainbow generalizations of ramsey theory: a survey, Graphs Combin., 26, 1-30 (2010) · Zbl 1231.05178 [10] Gallai, T., Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hung., 18, 25-67 (1967) · Zbl 0153.26002 [11] Gyárfás, A.; Sárközy, G., Gallai colorings of non-complete graphs, Discrete Math., 310, 977-980 (2010) · Zbl 1230.05128 [12] Gyárfás, A.; Sárközy, G.; Sebő, A.; Selkow, S., Ramsey-type results for gallai colorings, J. Graph Theory, 64, 233-243 (2010) · Zbl 1209.05082 [13] Hall, M.; Magnant, C.; Ozeki, K.; Tsugaki, M., Improved upper bounds for gallai-ramsey numbers of paths and cycles, J. Graph Theory, 75, 59-74 (2014) · Zbl 1280.05042 [14] Körner, J.; Simonyi, G., Graph pairs and their entropies: modularity problems, Combinatorica, 20, 227-240 (2000) · Zbl 0959.05040 [15] Liu, H.; Magnant, C.; Saito, A.; Schiermeyer, I.; Shi, Y., Gallai-Ramsey number for \(k_4 (2018)\), submitted for publication [16] Zhang, F.; Chen, Y.; Song, Z.-X., Gallai-Ramsey numbers of cycles (2018), submitted for publication This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.