Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings

Ali Ghalavand; Xueliang Li

paper

Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings

arXiv:2509.25949

Abstract

A subgraph in an edge-colored graph is called rainbow if all its edges have distinct colors. For a graph $G$ and an integer $n$ , the anti-Ramsey number $A R (n, G)$ is the maximum number of colors in an edge-coloring of $K_{n}$ that contains no rainbow copy of $G$ . We study $A R (n, k P_{3} \cup t P_{2})$ , where $k P_{3} \cup t P_{2}$ is the linear forest of $k$ disjoint paths on three vertices and a matching of size $t$ . Recently, Jie and Jin [Discrete Appl. Math. 386 (2026) 30-57] determined this number for $k \geq 2$ , $t \geq \frac{k ^{2} - 3 k + 4}{2}$ and $n = 2 t + 3 k$ . Here we solve the spanning case $n = 3 k + 2 t$ for all $k \geq 1$ , $t \geq 2$ with no extra restrictions.