×

Gallai-Ramsey numbers of odd cycles and complete bipartite graphs. (English) Zbl 1402.05146

Summary: For graphs \(G\) and \(H\) and integer \(k\geq 1\), the Gallai-Ramsey number \(\operatorname{gr}_k(G:H)\) is defined to be the minimum integer \(N\) such that if \(K_N\) is edge-colored with \(k\) colors, then there is either a rainbow \(G\) or a monochromatic \(H\). It is known that \[ \operatorname{gr}_k(K_3:C_{2n+1}) \] is exponential in \(k\). In this note, we improve the upper bound for \[ \operatorname{gr}_k(K_3:C_{2n+1}) \] obtained by M. Hall et al. [J. Graph Theory 75, No. 1, 59–74 (2014; Zbl 1280.05042)], and give bounds for \[ \operatorname{gr}_k(K_3:K_{m,n}). \]

MSC:

05C55 Generalized Ramsey theory
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1280.05042
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Axenovich, M., Choi, J.: A note on the monotonicity of mixed Ramsey numbers. Discrete Math. 311, 2020-2023 (2011) · Zbl 1223.05184 · doi:10.1016/j.disc.2011.05.030
[2] Chung, F., Graham, R.: Edge-colored complete graphs with precisely colored subgraphs. Combinatorica 3, 315-324 (1983) · Zbl 0529.05041 · doi:10.1007/BF02579187
[3] Day, A.N., Johnson, J.R.: Multicolor Ramsey numbers of odd cycles. J. Comb. Theory Ser. B 124, 56-63 (2017) · Zbl 1398.05213 · doi:10.1016/j.jctb.2016.12.005
[4] Faudree, R., Schelp, R.: All Ramsey numbers for cycles in graphs. Discrete Math. 8, 313-329 (1974) · Zbl 0294.05122 · doi:10.1016/0012-365X(74)90151-4
[5] Fujita, S., Magnant, C.: Extensions of Gallai-Ramsey results. J. Graph Theory 70, 404-426 (2012) · Zbl 1247.05149 · doi:10.1002/jgt.20622
[6] Fujita, S., Magnant, C.: Gallai-Ramsey numbers for cycles. Discrete Math. 311, 1247-1254 (2011) · Zbl 1222.05186 · doi:10.1016/j.disc.2009.11.004
[7] Fujita, S., Magnant, C., Ozeki, K.: Rainbow generalizations of Ramsey theory: a dynamic survey. Graphs Comb. 26, 1-30 (2010) · Zbl 1231.05178 · doi:10.1007/s00373-010-0891-3
[8] Gallai, T.: Transitiv orientierbare. Acta Math. Acad. Sci. Hung. 18, 24-66 (1967) · Zbl 0153.26002 · doi:10.1007/BF02020961
[9] 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
[10] Gyárfás, A., Simony, G.: Edge colorings of complete graphs without tricolored triangles. J. Graph Theory 46, 211-216 (2004) · Zbl 1041.05028 · doi:10.1002/jgt.20001
[11] 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 · doi:10.1002/jgt.21723
[12] Li, Y., Lih, K.: Multi-color Ramsey numbers of even cycles. Eur. J. Comb. 30, 114-118 (2009) · Zbl 1223.05186 · doi:10.1016/j.ejc.2008.02.008
[13] Li, Y., Tang, X., Zang, W.: Ramsey functions involving \[K_{m, n}\] Km,n with n large. Discrete Math. 300, 120-128 (2005) · Zbl 1073.05045 · doi:10.1016/j.disc.2005.01.008
[14] Łuczak, T., Simonovits, M., Skokan, J.: On the multi-colored Ramsey numbers of cycles. J. Graph Theory 69, 169-175 (2012) · Zbl 1242.05174 · doi:10.1002/jgt.20572
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.