Anti-Ramsey numbers for trees in complete multi-partite graphs

Abstract

Let $G$ be a complete multi-partite graph of order $n$. In this paper, we consider the anti-Ramsey number $ar(G,{\mathcal{T}}_q)$ with respect to $G$ and the set ${\mathcal{T}}_q$ of trees with $q$ edges, where $2\le q\le n-1$. For the case $q=n-1$, the result has been obtained by Lu, Meier and Wang. We will extend it to $q<n-1$. We first show that $ar(G,{\mathcal{T}}_q)={\ell }_q(G)+1$, where ${\ell }_q(G)$ is the maximum size of a disconnected spanning subgraph $H$ of $G$ with the property that any two components of $H$ together have at most $q$ vertices. Using this equality, we obtain the exact values of $ar(G,{\mathcal{T}}_q)$ for $n-3\le q\le n-1$. We also compute $ar(G,{\mathcal{T}}_q)$ by a simple algorithm when $(4n-2)/5\le q\le n-1$.

20 pages, 2 figures

References in corpus (2)

• Anti-Ramsey numbers for paths
• Turán numbers and anti-Ramsey numbers for short cycles in complete $3$-partite graphs