Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
rainbow graph; anti-Ramsey number; triangle
rainbow graph; anti-Ramsey number; triangle
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$.
References:
[1] Alon, N.: On a conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems. J. Graph Theory 7 (1983), 91-94. DOI 10.1002/jgt.3190070112 | MR 0693025 | Zbl 0456.05038
[2] Axenovich, M., Jiang, T., Kündgen, A.: Bipartite anti-Ramsey numbers of cycles. J. Graph Theory 47 (2004), 9-28. DOI 10.1002/jgt.20012 | MR 2079287 | Zbl 1062.05095
[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. DOI 10.1016/j.disc.2017.09.016 | MR 3724116 | Zbl 1376.05072
[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] 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. DOI 10.1016/j.disc.2021.112540 | MR 4291478 | Zbl 1472.05109
[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. DOI 10.37236/10628 | MR 4596343 | Zbl 1516.05099
[7] Gorgol, I.: Anti-Ramsey numbers in complete split graphs. Discrete Math. 339 (2016), 1944-1949. DOI 10.1016/j.disc.2015.10.038 | MR 3488930 | Zbl 1334.05084
[8] Gu, R., Li, J., Shi, Y.: Anti-Ramsey numbers of paths and cycles in hypergraphs. SIAM J. Discrete Math. 34 (2020), 271-307. DOI 10.1137/19M1244950 | MR 4057613 | Zbl 1431.05145
[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. DOI 10.1002/jgt.21803 | MR 3312135 | Zbl 1309.05107
[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. DOI 10.1016/j.amc.2023.128267 | MR 4623850 | Zbl 1545.05154
[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. DOI 10.1007/s00373-019-02053-y | MR 4003653 | Zbl 1426.05044
[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. DOI 10.1017/S096354830300590X | MR 2037072 | Zbl 1063.05100
[13] Jin, Z., Li, X.: Anti-Ramsey numbers for graphs with independent cycles. Electron. J. Comb. 16 (2009), Article ID R85, 8 pages. DOI 10.37236/174 | MR 2529794 | Zbl 1186.05052
[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. DOI 10.1016/j.amc.2019.124724 | MR 4007219 | Zbl 1433.05121
[15] Jin, Z., Zhong, K., Sun, Y.: Anti-Ramsey number of triangles in complete multipartite graphs. Graphs Comb. 37 (2021), 1025-1044. DOI 10.1007/s00373-021-02302-z | MR 4249217 | Zbl 1470.05113
[16] Li, Y., Liu, H., Hu, X.: Anti-Ramsey numbers for cycles in $n$-prisms. Discrete Appl. Math. 322 (2022), 1-8. DOI 10.1016/j.dam.2022.07.029 | MR 4469592 | Zbl 1498.05180
[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. DOI 10.1016/j.amc.2022.127277 | MR 4434814 | Zbl 1510.05211
[18] Montellano-Ballesteros, J. J., Neumann-Lara, V.: An anti-Ramsey theorem on cycles. Graphs Comb. 21 (2005), 343-354. DOI 10.1007/s00373-005-0619-y | MR 2190794 | Zbl 1075.05058
[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. DOI 10.1016/j.amc.2019.124888 | MR 4042657 | Zbl 1433.05220
[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. DOI 10.1016/j.disc.2022.113123 | MR 4470064 | Zbl 1502.05161
[21] Xu, J., Lu, M., Liu, K.: Anti-Ramsey problems for cycles. Appl. Math. Comput. 408 (2021), Article ID 126345, 7 pages. DOI 10.1016/j.amc.2021.126345 | MR 4264731 | Zbl 1510.05214
[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. DOI 10.48550/arXiv.1903.10319
Search
Partner of
