一类生成森林的反拉姆齐数
Anti-Ramsey Numbers of a Class of Spanning Forests
DOI: 10.12677/AAM.2026.156270, PDF,   
作者: 徐泓坚, 潘林舒*：浙江师范大学数学科学学院, 浙江 金华
关键词: 反拉姆齐数；线性森林；彩虹图；Anti-Ramsey Number； Linear Forests； Rainbow Graph
摘要: 给定边染色图G,若G任意两条边的颜色均不同,则称G为彩虹图.给定图G及其子图H, H在G中的反拉姆齐数,记作AR(G,H),表示最大颜色数k,使得存在图G的k-边染色,G中不包含彩虹子图H.本文将给出K2t+7中,P3, P4与匹配的并图所构成的短线性森林的反拉姆齐数精确值。
Abstract: Given an edge-colored graph G, if every two edges of G have distinct colors, then G is said to be a rainbow graph. For a graph G and its subgraph H , the anti-Ramsey number of H in G , denoted by AR(G, H) , is defined as the maximum integer k such that there exists a k-edge-coloring of G containing no rainbow subgraph isomorphic to H. In this paper, we determine the exact anti-Ramsey number for short linear forests consisting of the union of P3, P4 and matchings in K2t+7.
文章引用：徐泓坚, 潘林舒. 一类生成森林的反拉姆齐数[J]. 应用数学进展, 2026, 15(6): 102-113. https://doi.org/10.12677/AAM.2026.156270

参考文献

[1] Erdös, P., Simonovits, M. and Sós, V.T. (1975) Anti-Ramsey Theorems, Colloquia Mathemat- ica Societatis János Bolyai, Vol. 10. North-Holland Publishing Co., 633-643.
[2] Gilboa, S. and Roditty, Y. (2015) Anti-Ramsey Numbers of Graphs with Small Connected Components. Graphs and Combinatorics, 32, 649-662. [Google Scholar] [CrossRef] 
[3] He, M. and Jin, Z. (2025) Rainbow Short Linear Forests in Edge-Colored Complete Graph. Discrete Applied Mathematics, 361, 523-536. [Google Scholar] [CrossRef] 
[4] Jie, Q., He, M. and Jin, Z. (2025) Rainbow Forest Consisting of Short Paths in Kn. Discrete Applied Mathematics, 376, 260-269. [Google Scholar] [CrossRef] 
[5] Jie, Q. and Jin, Z. (2025) Anti-Ramsey Number of Union of 5-Path and Matching. Discussiones Mathematicae Graph Theory, 45, 1185-1210. [Google Scholar] [CrossRef] 
[6] Jie, Q. and Jin, Z. (2026) Rainbow-Free Colorings for Spanning Linear Forest Consisting of Short Paths. Discrete Applied Mathematics, 386, 30-57. [Google Scholar] [CrossRef] 
[7] Jin, Z., Jie, Q. and Cao, Z. (2024) Rainbow Disjoint Union of P4 and a Matching in Complete Graphs. Applied Mathematics and Computation, 474, Article ID: 128679. [Google Scholar] [CrossRef] 
[8] Xie, T. and Yuan, L. (2020) On the Anti-Ramsey Numbers of Linear Forests. Discrete Math- ematics, 343, Article ID: 112130. [Google Scholar] [CrossRef] 

为你推荐