×

Avoiding rainbow 2-connected subgraphs. (English) Zbl 1362.05086

Summary: While defining the anti-Ramsey number P. Erdős et al. [in: Infinite and finite sets. To Paul Erdős on his 60th birthday. Vol. I, II, III. Amsterdam - London: North-Holland Publishing Company. 633–643 (1975; Zbl 0316.05111)] mentioned that the extremal colorings may not be unique. In the paper we discuss the uniqueness of the colorings, generalize the idea of their construction and show how to use it to construct the colorings of the edges of complete split graphs avoiding rainbow 2-connected subgraphs. These colorings give the lower bounds for adequate anti-Ramsey numbers.

MSC:

05C55 Generalized Ramsey theory
05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0316.05111
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Erdős P., Simonovits A., Sós V., Anti-Ramsey theorems, In: (A. Hajnal, R. Rado, and V.Sós, eds.) Infinite and finite sets (Colloq. Math. Soc. J. Bolyai, North-Holland, 1973), 633-643; Erdős, P.; Simonovits, A.; Sós, V.; Hajnal, A.; Rado, R.; Sós, V., Infinite and finite sets, 633-643 (1973)
[2] Fujita S., Magnant C., Ozeki K., Rainbow Generalizations of Ramsey Theory: A Dynamic Survey, Theory and Applications of Graphs, firstly in Graphs and Combinatorics 26 (2010), 1-30; Fujita, S.; Magnant, C.; Ozeki, K., Rainbow Generalizations of Ramsey Theory: A Dynamic Survey, Theory and Applications of Graphs, firstly in Graphs and Combinatorics, 26, 1-30 (2010) · Zbl 1231.05178
[3] Axenovich M., Jiang T., Anti-Ramsey numbers for small complete bipartite graphs, Ars Combinatoria 73 (2004), 311-318; Axenovich, M.; Jiang, T., Anti-Ramsey numbers for small complete bipartite graphs, Ars Combinatoria, 73, 311-318 (2004) · Zbl 1072.05041
[4] Axenovich M., Jiang T., Kündgen A., Bipartite anti-Ramsey numbers of cycles, J. Graph Theory 47 (2004), 9-28; Axenovich, M.; Jiang, T.; Kündgen, A., Bipartite anti-Ramsey numbers of cycles, J. Graph Theory, 47, 9-28 (2004) · Zbl 1062.05095
[5] Axenovich M., Harborth H., Kemnitz A., Möller M., Schiermeyer I., Rainbows in the Hypercube, Graphs and Combinatorics 23 (2007), 123-133; Axenovich, M.; Harborth, H.; Kemnitz, A.; Möller, M.; Schiermeyer, I., Rainbows in the Hypercube, Graphs and Combinatorics, 23, 123-133 (2007) · Zbl 1118.05028
[6] Diestel R., Graph theory (Springer-Verlag, New York, 1997); Diestel, R., Graph theory (1997) · Zbl 0873.05001
[7] Alon N., On the conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory 7 (1983), 91-94; Alon, N., On the conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory, 7, 91-94 (1983) · Zbl 0456.05038
[8] Jiang T., West D.B., On the Erdős-Simonovits-Sós conjecture about the anti-Ramsey number of a cycle, Combin. Probab. Comput. 12 (2003), 585-598; Jiang, T.; West, D. B., On the Erdős-Simonovits-Sós conjecture about the anti-Ramsey number of a cycle, Combin. Probab. Comput., 12, 585-598 (2003) · Zbl 1063.05100
[9] Montellano-Ballesteros J.J., Neuman-Lara V., An anti-Ramsey theorem on cycles, Graphs and Combinatorics 21 (2005), 343-354; Montellano-Ballesteros, J. J.; Neuman-Lara, V., An anti-Ramsey theorem on cycles, Graphs and Combinatorics, 21, 343-354 (2005) · Zbl 1075.05058
[10] Gorgol I., Anti-Ramsey numbers in complete split graphs, Discrete Mathematics 339(7), (2016), 1944-1949; Gorgol, I., Anti-Ramsey numbers in complete split graphs, Discrete Mathematics, 339, 7, 1944-1949 (2016) · Zbl 1334.05084
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.