2025/11/08 by Ghalavand, Ali, Jie, Qing, Jin, Zemin +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2511.06034
openalex publication_date 2025/11/08 · openalex created_date 2025/11/12 · openalex updated_date 2026/07/28
According to a study by Erdős et al. in 1975, the anti-Ramsey number of a graph \(G\), denoted as \(AR(n, G)\), is defined as the maximum number of colors that can be used in an edge-coloring of the complete graph \(Kn\) without creating a rainbow copy of \(G\). In this paper, we investigate the anti-Ramsey number under edge deletion and demonstrate that both decreasing and unchanging are possible outcomes. For three non-negative integers \(k\), \(t\), and \(n\), let \(G = kP4 ∪ tP2\). Let \(E'\) be a subset of the edge set \(E(G)\) such that every endpoint of these edges has a degree of two in \(G\). We prove that if one of the conditions (i) \(t ≥ k + 1 ≥ 2\) and \(n ≥ 8k + 2t - 4\); (ii) \(k, t ≥ 1\) and \(n = 4k + 2t\); (iii) \(k = 1\), \(t ≥ 1\), and \(n ≥ 2t + 4\), occurs then the behavior of the anti-Ramsey number remains consistent when the edges in \(E'\) are removed from \(G\), i.e., \(AR(n, G) = AR(n, G - E')\). However, this is not the case when \(k ≥ 2\), \(t = 0\), and \(n=4k\). As a result, we calculate \(AR(kP4 ∪ tP2)\) for the cases: (i) \(t ≥ k + 1 ≥ 2\) and \(n ≥ 8k + 2t - 4\); (ii) \(k, t ≥ 1\) and \(n = 4k + 2t\); (iii) \(k = 1\), \(t ≥ 0\), and \(n ≥ 2t + 4\); (iv) \(k ≥ 1\), \(t = 0\), and \(n = 4k\).