On uniquely packable trees

2023/04/21 by Alex Alochukwu, Alochukwu, A., M. Dorfling +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2304.10889

openalex publication_date 2023/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An i-packing in a graph G is a set of vertices that are pairwise distance more than i apart. 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 χ_ρ-coloring and non-monotone χ_ρ-coloring respectively.

Related

• The Packing Coloring of Distance Graphs D(k,t)
• Generalizations of the Tree Packing Conjecture
• Packing colouring of some classes of cubic graphs
• Subdivision into i-packings and S-packing chromatic number of some lattices
• Packing chromatic number versus chromatic and clique number