Article
| Title: | On the mixed anti-Ramsey number for a matching and a clique (English) |
| Author: | Jie, Qing |
| Author: | Jin, Zemin |
| Author: | Sang, Lingyun |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 76 |
| Issue: | 3 |
| Year: | 2026 |
| Pages: | 917-925 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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 }$. (English) |
| Keyword: | $(G,H)$-good coloring |
| Keyword: | Ramsey number |
| Keyword: | mixed anti-Ramsey number |
| Keyword: | Turán number |
| MSC: | 05C35 |
| MSC: | 05C55 |
| MSC: | 05D10 |
| DOI: | 10.21136/CMJ.2026.0435-25 |
| . | |
| Date available: | 2026-09-11T13:14:15Z |
| Last updated: | 2026-09-14 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/153734 |
| . | |
| Reference: | [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. Zbl 1215.05051, MR 2595491, 10.37236/303 |
| Reference: | [2] Axenovich, M., Choi, J.: A note on the monotonicity of mixed Ramsey numbers.Discrete Math. 311 (2011), 2020-2023. Zbl 1223.05184, MR 2818879, 10.1016/j.disc.2011.05.030 |
| Reference: | [3] Axenovich, M., Iverson, P.: Edge-colorings avoiding rainbow and monochromatic subgraphs.Discrete Math. 308 (2008), 4710-4723. Zbl 1235.05092, MR 2438175, 10.1016/j.disc.2007.08.092 |
| Reference: | [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. Zbl 0316.05111, MR 0379258 |
| Reference: | [5] Fox, J., Sudakov, B.: Ramsey-type problem for an almost monochromatic $K_4$.SIAM J. Discrete Math. 23 (2009), 155-162. Zbl 1190.05085, MR 2476819, 10.1137/070706628 |
| Reference: | [6] Gallai, T.: Transitiv orientierbare Graphen.Acta Math. Acad. Sci. Hung. 18 (1967), 25-66 German. Zbl 0153.26002, MR 0221974, 10.1007/BF02020961 |
| Reference: | [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. Zbl 1230.05206, MR 2515759, 10.37236/257 |
| Reference: | [8] Li, X., Wang, L.: Gallai-Ramsey numbers for a class of graphs with five vertices.Graphs Comb. 36 (2020), 1603-1618. Zbl 1459.05202, MR 4163401, 10.1007/s00373-020-02194-5 |
| Reference: | [9] Lovász, L.: Kneser's conjecture, chromatic numbers, and homotopy.J. Comb. Theory, Ser. A 25 (1978), 319-324. Zbl 0418.05028, MR 0514625, 10.1016/0097-3165(78)90022-5 |
| Reference: | [10] Montellano-Ballesteros, J. J., Neumann-Lara, V.: An anti-Ramsey theorem.Combinatorica 22 (2002), 445-449. Zbl 1012.05092, MR 1932064, 10.1007/s004930200023 |
| Reference: | [11] Schiermeyer, I.: Rainbow numbers for matchings and complete graphs.Discrete Math. 286 (2004), 157-162 \99999DOI99999 10.1016/j.disc.2003.11.057 . Zbl 1053.05053, MR 2084292, 10.1016/j.disc.2003.11.057 |
| Reference: | [12] Turán, P.: Eine Extremalaufgabe aus der Graphentheorie.Mat. Fiz. Lapok 48 (1941), 436-452 Hungarian. Zbl 0026.26903, MR 0018405 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
