完全图中匹配和3-、4-路井图的反拉姆齐数
The Anti-Ramsey Number for the Union of a Matching, P 3 and P4 in a Complete Graph
DOI: 10.12677/AAM.2026.159386, PDF,   
作者: 潘林舒, 徐弘坚*：浙江师范大学数学科学学院, 浙江 金华
关键词: 反拉姆齐数；线性森林；彩虹图；Anti-Ramsey Number； Linear Forests； Rainbow Graph
摘要: 设G是一个简单图. 边染色图G称为彩虹图, 若图G的任意两条边的颜色均不同. 给定图G及其子 图H, H在G中的反拉姆齐数, 记作AR(G, H), 定义为最大整数k, 使得存在图G的k-边染色, 该染色 下G不含同构于H的彩虹子图. 本文给出完全图中, P3, P4与P3的井图的反拉姆数精确值.
Abstract: Let G be a simple graph. An edge-colored graph G is said to be rainbow if any two distinct edges of G receive different colors. 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 the union of P3, P4 and P2 in complete graphs.
文章引用：潘林舒, 徐弘坚. 完全图中匹配和3-、4-路井图的反拉姆齐数[J]. 应用数学进展, 2026, 15(9): 212-222. https://doi.org/10.12677/AAM.2026.159386

参考文献

[1] Erdo¨s, P., Simonovits, M. and Sos, V.T. (1975) Anti-Ramsey Theorems. In: Hajnal, A., Rado, R. and S´os, V.T., Eds., Infinite and Finite Sets: To Paul Erd¨os on His 60th Birthday, North- Holland Publishing Company, 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] Bialostocki, A., Gilboa, S. and Roditty, Y. (2015) Anti-Ramsey Numbers of Small Graphs. Ars Combinatoria, 123, 41-53.
[4] Jin, Z.M. and Gu, J.Q. (2024) Rainbow Disjoint Union of Clique and Matching in Edge-Colored Complete Graph. Discussiones Mathematicae Graph Theory, 44, 953-970. [Google Scholar] [CrossRef] 
[5] Fang, C.Q., Gy¨ori, E., Lu, M. and Xiao, J.M. (2021) On the Anti-Ramsey Number of Forests. Discrete Applied Mathematics, 291, 129-142. [Google Scholar] [CrossRef] 
[6] Xie, T.Y. and Yuan, L.T. (2020) On the Anti-Ramsey Numbers of Linear Forests. Discrete Mathematics, 343, Article ID: 112130. [Google Scholar] [CrossRef] 
[7] He, M.L. and Jin, Z.M. (2025) Rainbow Short Linear Forests in Edge-Colored Complete Graph. Discrete Applied Mathematics, 361, 523-536. [Google Scholar] [CrossRef] 
[8] Jie, Q., He, M.L. and Jin, Z.M. (2025) Rainbow Forest Consisting of Short Paths in Kn. Discrete Applied Mathematics, 376, 260-269. [Google Scholar] [CrossRef] 
[9] Jie, Q. and Jin, Z.M. (2025) Anti-Ramsey Number of Union of 5-Path and Matching. Discus- siones Mathematicae Graph Theory, 45, 1185-1210. [Google Scholar] [CrossRef] 
[10] Jie, Q. and Jin, Z.M. (2026) Rainbow-Free Colorings for Spanning Linear Forest Consisting of Short Paths. Discrete Applied Mathematics, 386, 30-57. [Google Scholar] [CrossRef] 
[11] Jin, Z.M., Jie, Q. and Cao, Z.X. (2024) Rainbow Disjoint Union of P4 and a Matching in Complete Graphs. Applied Mathematics and Computation, 474, Article ID: 128679. [Google Scholar] [CrossRef] 
[12] 徐涨坚, 潘林舒. 一类生成森林的反拉姆齐数[J]. 应用数学进展, 2026, 15(6): 102-113.

为你推荐