Article
| Title: | The anti-Ramsey problem for independent triangles in tripartite graphs (English) |
| Author: | Jin, Zemin |
| Author: | Liu, Huifang |
| Author: | Wang, Qian |
| Author: | Cao, Zhenxin |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 75 |
| Issue: | 4 |
| Year: | 2025 |
| Pages: | 1275-1289 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| Summary: | An edge colored graph is a rainbow if all colors on its edges are distinct. For two graphs $G$ and $H$, where $G$ contains $H$ as a subgraph, the anti-Ramsey number of $H$ in $G$, denoted by $AR(G, H)$, is the largest integer $k$ such that there exists a $k$-edge-coloring of $G$ containing no rainbow $H$. Let $kC_3$ denote the union of $k$ independent triangles. The anti-Ramsey problem for cycles (including independent cycles) in a complete graph $K_n$ has been studied well. We consider the problem for independent cycles in a tripartite graph and obtain the value of $AR(K_{q_1,q_2,q_3},2C_3)$ for $q_1\geq q_2\geq q_3\geq 2$. (English) |
| Keyword: | rainbow graph |
| Keyword: | anti-Ramsey number |
| Keyword: | triangle |
| MSC: | 05C35 |
| MSC: | 05C38 |
| MSC: | 05C55 |
| MSC: | 05D10 |
| DOI: | 10.21136/CMJ.2025.0060-25 |
| . | |
| Date available: | 2025-12-20T07:27:16Z |
| Last updated: | 2025-12-22 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/153242 |
| . | |
| Reference: | [1] Alon, N.: On a conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems.J. Graph Theory 7 (1983), 91-94. Zbl 0456.05038, MR 0693025, 10.1002/jgt.3190070112 |
| Reference: | [2] Axenovich, M., Jiang, T., Kündgen, A.: Bipartite anti-Ramsey numbers of cycles.J. Graph Theory 47 (2004), 9-28. Zbl 1062.05095, MR 2079287, 10.1002/jgt.20012 |
| Reference: | [3] Silva, J. De, Heysse, K., Kapilow, A., Schenfisch, A., Young, M.: Turán numbers of vertex-disjoint cliques in $r$-partite graphs.Discrete Math. 341 (2018), 492-496. Zbl 1376.05072, MR 3724116, 10.1016/j.disc.2017.09.016 |
| 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] Fang, C., Győri, E., Li, B., Xiao, J.: The anti-Ramsey numbers of $C_3$ and $C_4$ in complete $r$-partite graphs.Discrete Math. 344 (2021), Article ID 112540, 8 pages. Zbl 1472.05109, MR 4291478, 10.1016/j.disc.2021.112540 |
| Reference: | [6] Fang, C., Győri, E., Xiao, C., Xiao, J.: Turán numbers and anti-Ramsey numbers for short cycles in complete 3-partite graphs.Electron. J. Comb. 30 (2023), Article ID P2.35, 13 pages. Zbl 1516.05099, MR 4596343, 10.37236/10628 |
| Reference: | [7] Gorgol, I.: Anti-Ramsey numbers in complete split graphs.Discrete Math. 339 (2016), 1944-1949. Zbl 1334.05084, MR 3488930, 10.1016/j.disc.2015.10.038 |
| Reference: | [8] Gu, R., Li, J., Shi, Y.: Anti-Ramsey numbers of paths and cycles in hypergraphs.SIAM J. Discrete Math. 34 (2020), 271-307. Zbl 1431.05145, MR 4057613, 10.1137/19M1244950 |
| Reference: | [9] Horňák, M., Jendrol', S., Schiermeyer, I., Soták, R.: Rainbow numbers for cycles in plane triangulations.J. Graph Theory 78 (2015), 248-257. Zbl 1309.05107, MR 3312135, 10.1002/jgt.21803 |
| Reference: | [10] Hu, W., Li, Y., Liu, H., Hu, X.: Anti-Ramsey problems in the Mycielskian of a cycle.Appl. Math. Comput. 459 (2023), Article ID 128267, 10 pages. Zbl 1545.05154, MR 4623850, 10.1016/j.amc.2023.128267 |
| Reference: | [11] Jia, Y., Lu, M., Zhang, Y.: Anti-Ramsey problems in complete bipartite graphs for $t$ edge-disjoint rainbow spanning subgraphs: Cycles and matchings.Graphs Comb. 35 (2019), 1011-1021. Zbl 1426.05044, MR 4003653, 10.1007/s00373-019-02053-y |
| Reference: | [12] Jiang, T., West, D. B.: On the Erdős-Simonovits-Sós conjecture on the anti-Ramsey number of a cycle.Comb. Probab. Comput. 12 (2003), 585-598. Zbl 1063.05100, MR 2037072, 10.1017/S096354830300590X |
| Reference: | [13] Jin, Z., Li, X.: Anti-Ramsey numbers for graphs with independent cycles.Electron. J. Comb. 16 (2009), Article ID R85, 8 pages. Zbl 1186.05052, MR 2529794, 10.37236/174 |
| Reference: | [14] Jin, Z., Wang, F., Wang, H., Lv, B.: Rainbow triangles in edge-colored Kneser graphs.Appl. Math. Comput. 365 (2020), Article ID 124724, 6 pages. Zbl 1433.05121, MR 4007219, 10.1016/j.amc.2019.124724 |
| Reference: | [15] Jin, Z., Zhong, K., Sun, Y.: Anti-Ramsey number of triangles in complete multipartite graphs.Graphs Comb. 37 (2021), 1025-1044. Zbl 1470.05113, MR 4249217, 10.1007/s00373-021-02302-z |
| Reference: | [16] Li, Y., Liu, H., Hu, X.: Anti-Ramsey numbers for cycles in $n$-prisms.Discrete Appl. Math. 322 (2022), 1-8. Zbl 1498.05180, MR 4469592, 10.1016/j.dam.2022.07.029 |
| Reference: | [17] Liu, H., Lu, M., Zhang, S.: Anti-Ramsey numbers for cycles in the generalized Petersen graphs.Appl. Math. Comput. 430 (2022), Article ID 127277, 14 pages. Zbl 1510.05211, MR 4434814, 10.1016/j.amc.2022.127277 |
| Reference: | [18] Montellano-Ballesteros, J. J., Neumann-Lara, V.: An anti-Ramsey theorem on cycles.Graphs Comb. 21 (2005), 343-354. Zbl 1075.05058, MR 2190794, 10.1007/s00373-005-0619-y |
| Reference: | [19] Qin, Z., Lei, H., Li, S.: Rainbow numbers for small graphs in planar graphs.Appl. Math. Comput. 371 (2020), Article ID 124888, 7 pages. Zbl 1433.05220, MR 4042657, 10.1016/j.amc.2019.124888 |
| Reference: | [20] Wu, F., Zhang, S., Li, B., Xiao, J.: Anti-Ramsey numbers for vertex-disjoint triangles.Discrete Math. 346 (2023), Article ID 113123, 13 pages. Zbl 1502.05161, MR 4470064, 10.1016/j.disc.2022.113123 |
| Reference: | [21] Xu, J., Lu, M., Liu, K.: Anti-Ramsey problems for cycles.Appl. Math. Comput. 408 (2021), Article ID 126345, 7 pages. Zbl 1510.05214, MR 4264731, 10.1016/j.amc.2021.126345 |
| Reference: | [22] Yuan, L.-T., Zhang, X.-D.: Anti-Ramsey numbers of graphs with some decomposition family sequences.Available at https://arxiv.org/abs/1903.10319 (2019), 20 pages. 10.48550/arXiv.1903.10319 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
