Anti-Ramsey problems in the generalized Petersen graphs for cycles

2021/10/05 by Huiqing Liu, Mei Lu, Liu, Huiqing +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2110.01803

openalex publication_date 2021/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The anti-Ramsey number Ar(G,H) is the maximum number of colors in an edge-coloring of G with no rainbow copy of H. In this paper, we determine the exact anti-Ramsey number in the generalized Petersen graph P_n,k for cycles C_d, where 1≤ k≤ \lfloor (n-1)/(2) \rfloor and 5≤ d ≤ 6. We also give an algorithm to obtain the upper bound or lower bound of anti-Ramsey number.

Related

• The anti-Ramsey number of C₃ and C₄ in the complete r-partite graphs
• Anti-Ramsey numbers of graphs with some decomposition family sequences
• The anti-Ramsey numbers of cliques in complete multi-partite graphs
• Anti-Ramsey numbers for vertex-disjoint triangles
• On the anti-Ramsey number of forests