Anti-Ramsey numbers of graphs with small connected components

Abstract

The anti-Ramsey number, $AR(n,G)$, for a graph $G$ and an integer $n\ge |V(G)|$, is defined to be the minimal integer $r$ such that in any edge-colouring of $K_n$ by at least $r$ colours there is a multicoloured copy of $G$, namely, a copy of $G$ that each of its edges has a distinct colour. In this paper we determine, for large enough $n$, $AR(n,L\cup t{P}_2)$ and $AR(n,L\cup k{P}_3)$ for any large enough $t$ and $k$, and a graph $L$ satisfying some conditions. Consequently, we determine $AR(n,G)$, for large enough $n$, where $G$ is $P_3\cup t{P}_2$ for any $t\ge 3$, $P_4\cup t{P}_2$ and $C_3\cup t{P}_2$ for any $t\ge 2$, $k{P}_3$ for any $k\ge 3$, $t{P}_2\cup k{P}_3$ for any $t\ge 1$, $k\ge 2$, and $P_{t+1}\cup k{P}_3$ for any $t\ge 3$, $k\ge 1$. Furthermore, we obtain upper and lower bounds for $AR(n,G)$, for large enough $n$, where $G$ is $P_{k+1}\cup t{P}_2$ and $C_k\cup t{P}_2$ for any $k\ge 4$, $t\ge 1$.

Cited by in corpus (1)

• Monochromatic graph decompositions inspired by anti-Ramsey theory and the odd-coloring problem