完全多部图中4-圈的Anti-Ramsey数
Anti-Ramsey Number of 4-Cycle in Complete Multipartite Graphs
DOI: 10.12677/AAM.2021.107249, PDF,   
作者: 余 婷, 钟康云：浙江师范大学数学系，浙江 金华
关键词: Anti-Ramsey数；彩虹C4；完全多部图；Anti-Ramsey Number； Rainbow C4； Complete Multipartite Graph
摘要: 对于边染色图G，若G的每一条边都被染不同的颜色，则称G为彩虹图。对于给定的图G和H，使得G中不存在任何彩虹子图H的最大边染色数，叫做H在G中的anti-Ramsey数，记作AR(G,H)。本文确定了完全多部图中C4的anti-Ramsey数的精确值，研究结论覆盖了完全图和完全分裂图中的相关结果。
Abstract: A given edge-colored graph G is called rainbow if all its edges have distinct colors. Given two graphs G and H, the maximum colors in an edge-coloring of G without any rainbow H is called the anti-Ramsey number of H in G, which is denoted by AR(G,H). In this paper, we determine the anti-Ramsey number of 4-cycle in complete multipartite graphs. The results cover the results in complete and complete split graphs obtained previously.
文章引用：余婷, 钟康云. 完全多部图中4-圈的Anti-Ramsey数[J]. 应用数学进展, 2021, 10(7): 2378-2384. https://doi.org/10.12677/AAM.2021.107249

参考文献

[1] Erdös, P., Simonovits, M. and Sós, V.T. (1975) Anti-Ramsey Theorems, Infinite Finite Sets, Vol. II. Colloquia Mathematica Societatis Janos Bolyai, 10, 633-643.
[2] Fujita, S., Magnant, C. and Ozeki, K. (2010) Rainbow Generalizations of Ramsey Theory: A Survey. Graphs and Combinatorics, 26, 1-30. [Google Scholar] [CrossRef] 
[3] Fujita, S., Magnant, C. and Ozeki, K. (2014) Rainbow Generalizations of Ramsey Theory—A Dynamic Survey. Theory and Applications of Graphs, Article 1. [Google Scholar] [CrossRef] 
[4] Kano, M. and Li, X.L. (2008) Monochromatic and Heterochromatic Subgraphs in Edge-Colored Graphs—A Survey. Graphs and Combinatorics, 24, 237-263. [Google Scholar] [CrossRef] 
[5] Alon, N. (1983) On a Conjecture of Erdös, Simonovits and Sós Concerning Anti-Ramsey Theorems. Journal of Graph Theory, 1, 91-94. [Google Scholar] [CrossRef] 
[6] Jiang, T. and West, D.B. (2003) On the Erdös -Simonovits-Sós Conjecture on the Anti-Ramsey Number of a Cycle. Combinatorics, Probability and Computing, 12, 585-598. [Google Scholar] [CrossRef] 
[7] Axenovich, M., Jiang, T. and Kündgen, A. (2004) Bipartite Anti-Ramsey Numbers of Cycles. Journal of Graph Theory, 47, 9-28. [Google Scholar] [CrossRef] 
[8] Lv, B.H., Ye, K.C. and Wang, H.P. (2018) Rainbow Numbers for Small Cycles. Journal of Mathematics and Computer Science, 8, 297-303.

为你推荐