×

Properly colored \(C_4\)’s in edge-colored graphs. (English) Zbl 1448.05078

Summary: When many colors appear in edge-colored graphs, it is only natural to expect rainbow subgraphs to appear. This anti-Ramsey problem has been studied thoroughly and yet there remain many gaps in the literature. Expanding upon classical and recent results forcing rainbow triangles to appear, we consider similar conditions which force the existence of a properly colored copy of \(C_4\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C38 Paths and cycles
05C55 Generalized Ramsey theory
05D10 Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chartrand, G.; Lesniak, L.; Zhang, P., Graphs & Digraphs (2011), CRC Press: CRC Press Boca Raton, FL · Zbl 1211.05001
[2] Chen, H.; Li, X.; Tu, J., Complete solution for the rainbow numbers of matchings, Discrete Math., 309, 3370-3380 (2009) · Zbl 1218.05045
[3] J. Choi, A short proof of anti-ramsey number for cycles, manuscript.
[4] Chvátal, V.; Hammer, P. L., Set-Packing and Threshold GraphsUniv. Waterloo Res. Report (1973), CORR 73-21
[5] Erdős, P.; Simonovits, M.; Sós, V. T., Anti-ramsey theorems, (Infinite and Finite Sets (Colloq. Keszthely, 1973; Dedicated to P. Erdős on His 60th Birthday), II, Pages 633-643. Infinite and Finite Sets (Colloq. Keszthely, 1973; Dedicated to P. Erdős on His 60th Birthday), II, Pages 633-643, Colloq. Math. Soc. János Bolyai, vol. 10 (1975), North-Holland: North-Holland Amsterdam) · Zbl 0316.05111
[6] Erdős, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar, 10, 337-356 (1959), (unbound insert) · Zbl 0090.39401
[7] Fujita, S.; Magnant, C.; Ozeki, K., Rainbow generalizations of ramsey theory - a dynamic survey, Theory Appl. Graphs, 0, 1 (2014), article 1
[8] Fujita, S.; Ning, B.; Xu, C.; Zhang, S., On sufficient conditions for rainbow cycles in edge-colored graphs, Discrete Math., 342, 1956-1965 (2019) · Zbl 1414.05115
[9] Füredi, Z.; Simonovits, M., The history of degenerate (bipartite) extremal graph problems, (Lovász, L.; Ruzsa, I. Z.; Sós, V. T., Erd’́os Centennial. Erd’́os Centennial, Bolyai Society Mathematical Studies, Vol. 25 (2013), Springer: Springer Berlin, Heidelberg) · Zbl 1296.05098
[10] Kano, M.; Li, X., Monochromatic and heterochromatic subgraphs in edge-colored graphs - a survey, Graphs Combin., 24, 237-263 (2008) · Zbl 1190.05045
[11] Kövari, T.; Sós, V. T.; Turán, P., On a problem of K. Zarankiewicz, Colloquium Math., 3, 50-57 (1954) · Zbl 0055.00704
[12] Li, H., Raibow \(C_3\)’s and \(C_4\)’s in edge-colored graphs, Discrete Math., 313, 1893-1896 (2013) · Zbl 1277.05065
[13] Li, R.; Broersma, H.; Zhang, S., Properly edge-colored theta graphs in edge-colored complete graphs, Graphs Combin., 35, 261-286 (2019) · Zbl 1407.05097
[14] Li, B.; Ning, B.; Xu, C.; Zhang, S., Rainbow triangles in edge-colored graphs, European J. Combin., 36, 453-459 (2014) · Zbl 1284.05103
[15] Li, H.; Wang, G., Color degree and heterochromatic cycles in edge-colored graphs, European J. Combin., 33, 1958-1964 (2012) · Zbl 1248.05071
[16] Magnant, C.; Martin, D. M.; Salehi Nowbandegani, P., Monochromatic subgraphs in the absence of a properly colored \(4\)-cycle, Graphs Combin., 34, 1147-1158 (2018) · Zbl 1402.05075
[17] Manoussakis, Y.; Spyratos, M.; Zs. Tuza, P.; Voigt, M., Minimal colorings for properly colored subgraphs, Graphs Combin., 12, 345-360 (1996) · Zbl 0864.05035
[18] Montellano-Ballesteros, J. J.; Neumann-Lara, V., An anti-ramsey theorem, Combinatorica, 22, 445-449 (2002) · Zbl 1012.05092
[19] Montellano-Ballesteros, J. J.; Neumann-Lara, V., An anti-Ramsey theorem on cycles, Graphs Combin., 21, 343-354 (2005) · Zbl 1075.05058
[20] Schiermeyer, I., Rainbow numbers for matchings and complete graphs, Discrete Math., 286, 157-162 (2004) · Zbl 1053.05053
[21] Xu, C.; Hu, X.; Wang, W.; Zhang, S., Rainbow cliques in edge-colored graphs, European J. Combin., 54, 193-200 (2016) · Zbl 1331.05091
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.