Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
$(G,H)$-good coloring; Ramsey number; mixed anti-Ramsey number; Turán number
$(G,H)$-good coloring; Ramsey number; mixed anti-Ramsey number; Turán number
Summary:
Given two graphs $G$ and $H$, an edge-coloring of the complete graph $K_n$ is called a $(G,H)$-good coloring if it contains neither a monochromatic copy of $G$ nor a rainbow copy of $H$. Let $R(n;G,H)$ denote the set of integers $k$ for which a $(G,H)$-good $k$-coloring of $K_n$ exists. The numbers $\max R(n;G,H)$ and $\min R(n;G,H)$ are called the mixed anti-Ramsey numbers. We determine these numbers for $G = 2K_2$ and $H = K_s$ with $3\le s\le n$. We show that $\min R(n;2K_2,K_s)=n-2$ for all $s$. For $\max R(n;2K_2,K_s)$, we prove that if $s=2k+1$ then $\max R(n;2K_2,K_s) = t_n^k + n - k$, where $t_n^k$ is the Tuán number for $K_{k+1}$. If $s=2k+2$ and $s > \sqrt {2n-{7\over 4}}+ {1\over 2}$, then $\max R(n;2K_2,K_s) = t_{n-1}^k + 2n - k - 2$. The latter result reveals a connection between $\max R$ and the Turán number of $K_{\lfloor {s-1\over 2}\rfloor }$.
References:
[1] Axenovich, M., Choi, J.: On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph. Electron. J. Comb. 17 (2010), Article ID R31, 15 pages. DOI 10.37236/303 | MR 2595491 | Zbl 1215.05051
[2] Axenovich, M., Choi, J.: A note on the monotonicity of mixed Ramsey numbers. Discrete Math. 311 (2011), 2020-2023. DOI 10.1016/j.disc.2011.05.030 | MR 2818879 | Zbl 1223.05184
[3] Axenovich, M., Iverson, P.: Edge-colorings avoiding rainbow and monochromatic subgraphs. Discrete Math. 308 (2008), 4710-4723. DOI 10.1016/j.disc.2007.08.092 | MR 2438175 | Zbl 1235.05092
[4] Erdös, P., Simonovits, M., Sós, V. T.: Anti-Ramsey theorems. Infinite finite Sets Colloquia Mathematica Societatis János Bolyai 10. North-Holland, Amsterdam (1975), 633-643. MR 0379258 | Zbl 0316.05111
[5] Fox, J., Sudakov, B.: Ramsey-type problem for an almost monochromatic $K_4$. SIAM J. Discrete Math. 23 (2009), 155-162. DOI 10.1137/070706628 | MR 2476819 | Zbl 1190.05085
[6] Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. 18 (1967), 25-66 German. DOI 10.1007/BF02020961 | MR 0221974 | Zbl 0153.26002
[7] Jungić, V., Kaiser, T., Kráľ, D.: A note on edge-colourings avoiding rainbow $K_4$ and monochromatic $K_m$. Electron. J. Comb. 16 (2009), Article ID N19, 9 pages. DOI 10.37236/257 | MR 2515759 | Zbl 1230.05206
[8] Li, X., Wang, L.: Gallai-Ramsey numbers for a class of graphs with five vertices. Graphs Comb. 36 (2020), 1603-1618. DOI 10.1007/s00373-020-02194-5 | MR 4163401 | Zbl 1459.05202
[9] Lovász, L.: Kneser's conjecture, chromatic numbers, and homotopy. J. Comb. Theory, Ser. A 25 (1978), 319-324. DOI 10.1016/0097-3165(78)90022-5 | MR 0514625 | Zbl 0418.05028
[10] Montellano-Ballesteros, J. J., Neumann-Lara, V.: An anti-Ramsey theorem. Combinatorica 22 (2002), 445-449. DOI 10.1007/s004930200023 | MR 1932064 | Zbl 1012.05092
[11] Schiermeyer, I.: Rainbow numbers for matchings and complete graphs. Discrete Math. 286 (2004), 157-162 \99999DOI99999 10.1016/j.disc.2003.11.057 . DOI 10.1016/j.disc.2003.11.057 | MR 2084292 | Zbl 1053.05053
[12] Turán, P.: Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. MR 0018405 | Zbl 0026.26903
Search
Partner of
