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.