On uniquely packable trees

Abstract

An $i$-packing in a graph $G$ is a set of vertices that are pairwise distance more than $i$ apart. A \emph{packing colouring} of $G$ is a partition $X=\{X_1,X_2,\dots ,X_k\}$ of $V(G)$ such that each colour class $X_i$ is an $i$-packing. The minimum order $k$ of a packing colouring is called the packing chromatic number of $G$, denoted by $\ddot{I}{‡}_{\ddot{I}}(G)$. In this paper we investigate the existence of trees $T$ for which there is only one packing colouring using $\ddot{I}{‡}_{\ddot{I}}(T)$ colours. For the case $\ddot{I}{‡}_{\ddot{I}}(T)=3$, we completely characterise all such trees. As a by-product we obtain sets of uniquely $3$-$\ddot{I}{‡}_{\ddot{I}}$-packable trees with monotone $\ddot{I}{‡}_{\ddot{I}}$-coloring and non-monotone $\ddot{I}{‡}_{\ddot{I}}$-coloring respectively.