Rainbow-free colorings for spanning linear forest consisting of short paths
Abstract
An edge-colored graph G is called rainbow if all edges in G are assigned distinct colors. The anti-Ramsey number A R ( G , H ) , defined as the maximum number of colors in an edge-coloring of G avoiding rainbow copies of H , has been extensively studied for graphs with disjoint unions small components. In this paper, we focus on H = k P 3 ∪ t P 2 . Previous work determined the exact value of A R ( K n , k P 3 ∪ t P 2 ) for all n ≥ 2 t + 3 k + 1 under the constrain t ≥ k 2 − k + 4 2 . Notably, the case n = 2 t + 3 k remains open. In this paper, we solve this gap by rigorously establishing the anti-Ramsey number for n = 2 t + 3 k and under the constrain t ≥ k 2 − 3 k + 4 2 , thereby completing the characterization across all n .
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Discrete Applied Mathematics
- Publisher
- Elsevier BV
- Volume
- 386
- Pages
- 30–57
- Publication date
- 3 February 2026
- Language
- EN