平面三角剖分图中非连通图的Anti-Ramsey数  

The Anti-Ramsey Number of Unconnected Graphs in Plane Triangulation Graphs

作　　者：罗冬连 顾俊琪 

机构地区：[1]浙江师范大学数学科学学院,浙江 金华

出　　处：《应用数学进展》2023年第6期3030-3038,共9页Advances in Applied Mathematics

摘　　要：给定图 G 的一个边染色,如果图 G 的任意两条边颜色都不相同, 那么就说图 G 是彩虹的。 图 H 在图 G 中的 anti-Ramsey 数是使得边染色图 G 中不存在任何彩虹子图 H 的最大颜色数。 图的 anti-Ramsey 数目前得到广泛的研究, 尤其是匹配在多种图类中的 anti-Ramsey 数得到广泛而 深入的研究。 Gilboa 和Roditty 研究了由小的连通分支构成的图在完全图中的 anti-Ramsey 数,而非连通图在平面图中的 anti-Ramsey 数除匹配外结果较少。 本论文将继续以这个方向研究边染色图中 C3 ∪ tP2 这个非连通图在平面三角剖分图中的 anti-Ramsey 数,得到了对任意n ≥ 2t + 3, t ≥ 2, 2n + 3t − 9 ≤ AR(Tn, C3 ∪ tP2) ≤ 2n + 4t − 5。Given an edge-coloring of a graph G, G is said to be rainbow if any two edges of G receive different colors. Given two graphs G and H, the anti-Ramsey number of H in G is defined to be the maximum number of colors in an edge-colored graph G which contains no rainbow copies of H. The anti-Ramsey numbers for graphs, especially matchings, have been studied in several graph classes. Gilboa and Roditty focused on the anti-Ramsey number of graphs with small components, but the results of the anti-Ramsey number of graphs with small components in plane graph are few. In this paper, we continue the work in this direct and determine the anti-Ramsey number of C3 ∪ tP2 in plane triangulations, then we can get 2n + 3t − 9 ≤ AR(Tn, C3 ∪ tP2) ≤ 2n + 4t − 5 for n ≥ 2t + 3, t ≥ 2.

关 键 词：彩虹匹配 Anti-Ramsey数 平面三角剖分 

分 类 号：G63[文化科学—教育学]