×

Gallai-Ramsey numbers of \(C_7\) with multiple colors. (English) Zbl 1405.05054

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.

MSC:

05C15 Coloring of graphs and hypergraphs
05D10 Ramsey theory
PDFBibTeX XMLCite
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.