The anti-Ramsey numbers of cliques in complete multi-partite graphs

2024/01/03 by Yuyu An, An, Yuyu, Ervin Győri +3 · 1 citation
Computer Science · Mathematics · #05D10 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2401.01766

openalex publication_date 2024/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. Let G and H be two graphs. The anti-Ramsey number \ar(G, H) is the maximum number of colors of an edge-coloring of G that does not contain a rainbow copy of H. In this paper, we study the anti-Ramsey numbers of K_k in complete multi-partite graphs. We determine the values of the anti-Ramsey numbers of K_k in complete k-partite graphs and in balanced complete r-partite graphs for r≥ k.

Cited by

• Exact rainbow numbers of cycle-related graphs in multi-hubbed wheels

Related

• The anti-Ramsey number of C₃ and C₄ in the complete r-partite graphs
• Anti-Ramsey number of intersecting cliques
• On the anti-Ramsey number of forests
• Anti-Ramsey Number of Friendship Graphs
• Anti-Ramsey numbers for vertex-disjoint triangles