On uniquely packable trees

Abstract

An i-packing in a graph G is a set of vertices that are pairwise at distance more than i. A packing colouring of G is a partition X = {X₁,X₂, . . . ,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 χρ(G). In this paper we investigate the existence of trees T for which there is only one packing colouring using χρ(T) colours. For the case χρ(T) = 3, we completely characterise all such trees. As a by-product we obtain sets of uniquely 3-χρ-packable trees with monotone χρ-colouring and non-monotone χρ-colouring respectively.