Quaestiones Mathematicae

ISSN: (Print) (Online) Journal homepage: www.tandfonline.com/journals/tqma20

On uniquely packable trees

A. Alochukwu, M. Dorfling & E. Jonck

To cite this article: A. Alochukwu, M. Dorfling & E. Jonck (2024) On uniquely packable trees,
Quaestiones Mathematicae, 47:7, 1353-1368, DOI: 10.2989/16073606.2024.2321259

To link to this article:  https://doi.org/10.2989/16073606.2024.2321259

Published online: 21 Mar 2024.

Submit your article to this journal 

Article views: 27

View related articles 

View Crossmark data

Citing articles: 1 View citing articles 

Full Terms & Conditions of access and use can be found at
https://www.tandfonline.com/action/journalInformation?journalCode=tqma20

https://www.tandfonline.com/journals/tqma20?src=pdf
https://www.tandfonline.com/action/showCitFormats?doi=10.2989/16073606.2024.2321259
https://doi.org/10.2989/16073606.2024.2321259
https://www.tandfonline.com/action/authorSubmission?journalCode=tqma20&show=instructions&src=pdf
https://www.tandfonline.com/action/authorSubmission?journalCode=tqma20&show=instructions&src=pdf
https://www.tandfonline.com/doi/mlt/10.2989/16073606.2024.2321259?src=pdf
https://www.tandfonline.com/doi/mlt/10.2989/16073606.2024.2321259?src=pdf
http://crossmark.crossref.org/dialog/?doi=10.2989/16073606.2024.2321259&domain=pdf&date_stamp=21%20Mar%202024
http://crossmark.crossref.org/dialog/?doi=10.2989/16073606.2024.2321259&domain=pdf&date_stamp=21%20Mar%202024
https://www.tandfonline.com/doi/citedby/10.2989/16073606.2024.2321259?src=pdf
https://www.tandfonline.com/doi/citedby/10.2989/16073606.2024.2321259?src=pdf
https://www.tandfonline.com/action/journalInformation?journalCode=tqma20


Quaestiones Mathematicae 2024, 47(7): 1353–1368

© 2024 NISC (Pty) Ltd

https://doi.org/10.2989/16073606.2024.2321259

ON UNIQUELY PACKABLE TREES

A. Alochukwu*

Department of Mathematics, Computer Science and Physics, Albany State University,
USA, and

DSI-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS),
South Africa.

E-Mail alex.alochukwu@asurams.edu alex.alochukwu@wits.ac.za

M. Dorfling

Department of Mathematics and Applied Mathematics, University of Johannesburg,
South Africa.

E-Mail mdorfling0@gmail.com

E. Jonck

School of Mathematics, University of the Witwatersrand, Johannesburg, South Africa,
and

DSI-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS),
South Africa.

E-Mail Betsie.Jonck@wits.ac.za

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 = {X1, X2, . . . , Xk} of V (G)
such that each colour class Xi 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.

Mathematics Subject Classification (2020): 05C15, 05C70.

Key words: Colouring, broadcast, packing, tree, uniquely colourable, monotone colouring,
packing chromatic number.

1. Introduction. Packing colourings were inspired by a frequency assignment
problem in broadcasting. The distance between broadcasting stations is directly
related to the frequency they may receive, since two stations may only be assigned
the same frequency if they are located far enough apart for their frequencies not
to interfere with each other. This colouring was first introduced by Goddard et

*Corresponding author. Financial support by the DSI-NRF Centre of Excellence in Mathe-
matical and Statistical Sciences (CoE-MaSS), South Africa, is gratefully acknowledged.

Quaestiones Mathematicae is co-published by NISC (Pty) Ltd and Informa UK Limited
(trading as the Taylor & Francis Group)



1354 A. Alochukwu, M. Dorfling and E. Jonck

al. [14] where it was called broadcast colouring. Brešar et al. [5] were the first to
use the term packing colouring.

Let G = (V (G), E(G)) be a simple graph of order n and let i be a positive
integer. A set X ⊆ V (G) is called an i-packing if vertices in X are pairwise distance
more than i apart. A packing colouring of G is a partition X = {X1, X2, . . . , Xk}
of V (G) such that each colour class Xi is an i-packing. Hence, two vertices may be
assigned the same colour if the distance between them is greater than the colour.
The minimum order k of a packing colouring is called the packing chromatic number
of G, denoted by χρ(G).

Note that every packing colouring is a proper colouring. For terms and concepts
not defined here, see [7].

Goddard et al. [14] investigated among other things, the packing chromatic
number of paths, trees and the infinite square lattice, Z2. They found that for a
tree of diameter two (that is, a star) the packing chromatic number is 2; for a tree
of diameter three the packing chromatic number is 3, and for a tree of diameter 4,
they gave an explicit formula based on the number of large neighbors (degree 4 or
more) and small neighbors (degree 3 or less) of the central vertex. They proved
also that for all trees T of order n it holds that χρ(T ) ≤ n+7

4 , except when n = 4 or
n = 8 (when the bound is 1

4 more) and these bounds are sharp. Furthermore they
proved that the minimum order of a tree T with χρ(T ) = 2, is 2; for a tree T with
χρ(T ) = 3, the minimum order is 4 and for a tree with χρ(T ) = 4, the minimum
order is 8.

The packing chromatic number of lattices, trees, and Cartesian products in
general is also considered in [5, 18, 17, 8, 11, 12] and [15]. Determining the packing
chromatic number is considered to be difficult. Finding χρ for general graphs is
NP-hard [14], and in fact, deciding whether χρ(G) ≤ 4 is already NP-complete.
In [10], Fiala and Golovach showed that the decision whether a tree allows a packing
colouring with at most k classes is NP-complete.

Brešar, Klavžar and Rall introduced monotone colourings in [5]. Let G be a
graph. For a colouring c : V (G) → {1, . . . , k}, and a colour l, 1 ≤ l ≤ k, we denote
by cl the cardinality of the class of vertices coloured by l. A χρ(G)-colouring is
monotone if c1 ≥ c2 ≥ · · · ≥ ck. They proved that for any graph G and any l,

where l ≤
⌊
χρ(G)

2

⌋
, there exists a χρ(G)-colouring c : V (G) → {1, ..., k} such that

cl ≥ cj for all j ≥ 2l. Note that this implies that for any graph G there exists an
optimal colouring in which c1 ≥ ci for 2 ≤ i ≤ k. They also showed however, that
there exists a class of trees Tk, k ≥ 2, in which no optimal colouring is monotone.
The authors proved that for any k ≥ 2, χρ(Tk) = 3 and moreover, there exists a
unique optimal colouring of Tk with c1 = k+5, c2 = 2 and c3 = k+1. In particular,
c3 > c2.

Several researchers have also investigated related topics on the packing chro-
matic number and packing colourings for specific graph types, see [3, 6, 1, 2, 9, 13,
19] for results on cubic graphs, subdivided plane graphs, Petersen graphs, Moore
graphs, subcubic outerplanar graphs etc. In addition, an integer linear program-
ming and a satisfiability test model for the packing colouring problem of graphs
were developed in [16]. The proposed models in [16] outperforms other exact meth-



On uniquely packable trees 1355

ods such as a back-tracking and dynamic algorithm.
Given the volume of publications that have been written on the packing chro-

matic number and its growing interest, we refer the reader to the survey article [4]
on packing colourings by Brešar et al. for more details.

We call a graph G uniquely k-χρ-packable if χρ(G) = k and G has a unique
packing colouring of order k. By uniqueness of a packing colouring we mean unique-
ness up to identity. In other words, we work with labelled graphs. For instance,
K2 has packing chromatic number 2, but is not uniquely 2-χρ-packable.

The following terminology is used throughout: Given a graph G and a colouring
of V (G), an i-vertex is a vertex of colour i. We similarly use the terms i-neighbour
and i-leaf. We also use these terms if G is uniquely colourable, even if no colouring
is specified.

In this paper we investigate uniquely-packable trees. We characterise the
uniquely 3-χρ-packable trees, and investigate the existence of uniquely k-χρ-pack-
able trees for k > 3. Our characterisation is constructive. We proved that a
tree is uniquely 3-χρ-packable if and only if it can be constructed from one of the
three trees described in Figure 1 by iteratively applying some finite sequence of
operations as described in 2.1. Furthermore, we showed that the monotonicity of
the packing colourings can also be determined by performing the same operations.
As a by-product of our investigation, we obtain sets of uniquely 3-χρ-packable trees
with monotone χρ-colouring and non-monotone χρ-colouring respectively.

The remainder of this paper is organised as follows. In Section 2 we characterise
those trees that are uniquely 3-χρ-packable and describe all operations that would
be useful when constructing uniquely 3-χρ-packable trees. Section 3 investigates the
monotonicity of the packing colourings, by considering the three graphs, from which
all uniquely 3-χρ-packable trees are constructed and show that their colourings
are monotone. This leads us to establishing sets of uniquely 3-χρ-packable trees
with monotone χρ-colouring and non-monotone χρ-colouring respectively. In the
concluding Section 4.1 we considered the existence of uniquely k-χρ-packable trees
for k > 3 and present a way to construct such trees for 4 ≤ k ≤ 7.

2. Uniquely 3-χρ-packable trees. In this section we characterise those trees
that are uniquely 3-χρ-packable. The special case of Claim 1 with k = 3 and
Lemma 1 will be used repeatedly throughout this section.

Claim 1. If c is a k-χρ-packing of a graph G, then every 1-vertex v has degree at
most k − 1.

Proof. Since no two neighbours of v can have the same colour because of the
distance restraint between vertices of the same colour, v is adjacent to at most
k − 1 vertices. 2

Lemma 1. If c is a 3-χρ-packing of a graph G with a 2-vertex x adjacent to a
3-vertex y, then all neighbours of x other than y have colour 1 and these vertices
have no neighbours other than x.



1356 A. Alochukwu, M. Dorfling and E. Jonck

Proof. Clearly, vertices of G can only be coloured with colours 1, 2 or 3 since
c is a 3-χρ-packing of the graph G. As a result, all neighbours of x other than y
can only have colour 1 because colour 2 and colour 3 are not possible due to the
distance constraint in the definition of a packing colouring. In addition, observe
that a 1-neighbour of the 2-vertex x does not have any new neighbour since since
such a vertex can’t be coloured in a 3-χρ-packing of G. 2

2.1. Characterisation of uniquely 3-χρ-packable trees. Our characterisa-
tion is constructive. We start with one of the coloured trees depicted in Figure 1,
and iteratively apply one of the operations described below and depicted in Fig-
ure 2. This produces all uniquely 3-χρ-packable trees, and only such trees, with
the unique 3-colouring assigned.

F1

2 1

1

3
1

2

1

F2

3 1

1

2
1

2

1

1 3

F3

3
1 2

2

1

1 3

11 2

121

1

Figure 1: The three graphs from which all uniquely 3-χρ-packable trees are con-
structed.

O1 Attach a new 1-vertex to a 2-vertex.

O2 Attach a new 1-vertex to a 3-vertex that has a 2-neighbour.

O3 Attach a new 2-vertex to a 1-vertex that has no 2-neighbours.

O4 Attach a new 3-vertex to a 1-vertex that is at distance at least 3 from all
3-vertices.

O5 Let u be a 3-vertex. Add a path P : v1, v2, v3, and the edge uv1. Give v1, v2
and v3 the colours 1, 2 and 1, respectively.

Note that O5 is a combination of O2,O3 and O1 if u has a 2-neighbour.

O6 Let u be a 3-vertex with no 2-neighbour. Add a path P : v1, v2, v3, and the
edge uv2. Give v1, v2, and v3 the colours 1, 2 and 1, respectively.



On uniquely packable trees 1357

O7 Replace an edge uv, where c(u) = 3, c(v) = 1, and deg(u) = 2, with a path
u,w1, w2, w3, w4, v. Assign the colours 1,2,1 and 3 to w1, w2, w3, and w4,
respectively.

O1
2 1 O2

2 3 1

O3
1 2 O4

1 3

O5
3 1 2 1 O6

3 2 1

1

→O7
3 1 3 1 2 1 3 1

Figure 2: The seven operations used to construct all uniquely 3-χρ-packable trees.

Lemma 2.

1 F1, F2 and F3 are uniquely 3-χρ-packable.

2 If any of the operations Oi is applied to a uniquely 3-χρ-packable tree T ′, the
resulting tree T is uniquely 3-χρ-packable.

3 If a uniquely 3-χρ-packable tree T is obtained from a tree T ′ using operation O7,
then T ′ is uniquely 3-χρ-packable.

Proof.

1 This is easily verified by inspection.

2 In the case of O2, O5 or O6, the new vertices can only be coloured in one
way, given the colours of the existing vertices.

For O1, note that the existing 2-vertex must be at distance at most 2 from
a 3-vertex, otherwise T ′ is a star, which is not uniquely 3-χρ-packable. The
new vertex can therefore only receive colour 1. Similar arguments apply to
O3 and O4.

Next, we prove the lemma for the case of O7.

Let T be obtained from T ′ by O7, and let u, v and wi be as in the description
of O7. Let c

′ be the unique 3-χρ-packing of T ′ and let c be a 3-χρ-packing of
T that differs from the 3-χρ-packing produced by O7.



1358 A. Alochukwu, M. Dorfling and E. Jonck

If c(u) = 3 and c(v) = 1, there is only one way to colour the wi’s, and
restricting c to T ′ yields a 3-χρ-packing of T ′ different from c′, contradicting
the uniqueness of c′. Similarly if c(u) = 1 and c(v) = 3, or c(u) = 2 and
c(v) = 1, or c(u) = 1 and c(v) = 2.

Suppose c(u) = 3 and c(v) = 2. Again there is only one way to colour
the wi’s (c(w1) = 1, c(w2) = 2, c(w3) = 1, c(w4) = 3). Now suppose that
restricting c to T ′ does not yield a proper colouring. Then the neighbour x
of u other than w1 must have colour 2. Since c(w4) = 3 and c(v) = 2, and
c(u) = 3 and c(x) = 2, it follows that T ′ is obtained from two stars with
centers corresponding to x and v by identifying a leaf (corresponding to u)
from each. But such a graph is not uniquely 3-χρ-packable.

A similar argument applies if c(u) = 2 and c(v) = 3.

We cannot have c(u) = c(v) = 2 or c(u) = c(v) = 3, since there is no way
to colour the wi’s. That leaves c(u) = c(v) = 1: The only possibility is for
w1, w2, w3 and w4 to be coloured 2, 1, 3 and 2, respectively. (The fact that
u has degree 2 eliminates 2, 3, 1, 2.) So v has degree 1 and we can change
its colour to 2 and restrict to T ′ to obtain a valid colouring of T ′ that differs
from c′ on u.

3 Let c be the unique 3-χρ-packing of T , suppose that T ′ is not uniquely 3-χρ-
packable and let c′ be a 3-χρ-packing that differs from c on T ′. Let u and v be
the 3- and 1-vertices (under c) of T ′ to which O7 is applied, respectively. We
consider the following cases: (Note that cases 2, 4, and 6 are not symmetric
to their counterparts, because of the degree constraint on u. This only plays
a role in Case 5 and Case 6 though.)

Case 1: c′(u) = 3 and c′(v) = 1.
We extend c′ to T by colouring w1, w2, w3 and w4 with 1, 2, 1 and 3,
respectively, to contradict the uniqueness of c.

Case 2: c′(u) = 1 and c′(v) = 3.
We can reverse the sequence of colours in Case 1 above, that is extend c′ to
T by colouring w1, w2, w3 and w4 with 3,1,2 and 1, respectively.

Case 3: c′(u) = 3 and c′(v) = 2.
We extend c′ to T by colouring w1, w2, w3 and w4 with 1, 2, 1 and 3,
respectively.

Case 4: c′(u) = 2 and c′(v) = 3.
We reverse the sequence in Case 3, that is extend c′ to T by colouring w1,
w2, w3 and w4 with 1, 3, 1 and 2, respectively, to contradict the uniqueness
of c.

Case 5: c′(u) = 1 and c′(v) = 2.
The other neighbour w of u can only have c′(w) = 3, so v has no 3-neighbour
under c′ and we can extend c′ to T by colouring w1, w2, w3 and w4 with 2,
1, 3 and 1, respectively..

Case 6: c′(u) = 2 and c′(v) = 1.
If the other neighbour w of u has c′(w) = 1, we extend c′ to T by colouring



On uniquely packable trees 1359

w1, w2, w3 and w4 with 1, 3, 1 and 2, respectively. Otherwise, c′(w) = 3, so
by Lemma 1, v has no other neighbours. Here we change the colour of u to
1, and colour w1, w2, w3 and w4 with 2, 1, 3 and 2, respectively. Although
we changed the colour of u, the extended colouring does differ from c because
c′(w) = 3 but c(w) ̸= 3 as c(u) = 3.

All other cases are ruled out by the fact that uv is an edge of T ′. 2

Lemma 3. If G is a uniquely 3-χρ-packable graph, then G has a 2-vertex adjacent
to a 3-vertex.

Proof. Let c be the unique 3-χρ-packing of G and suppose no 2-vertex is adjacent
to a 3-vertex. Then no two 2-vertices x and y are at distance 3, otherwise both u
and v on any path x, u, v, y must have colour 1. But then we can interchange the
colour classes 2 and 3, contradicting the uniqueness of c. 2

Lemma 4. Let F ⊆ T be trees, where F is uniquely 3-χρ-packable, and let v be
any 3-vertex of F . For any 3-χρ-packing c of T , the 3-vertices are precisely those
vertices whose distance from v is a multiple of 4.

Proof. Let u be any vertex other than v and consider the unique v–u path
P : v, v1, . . . , vk = u. There are two possibilities for c(v1), that is, c(v1) = 2 or
c(v1) = 1. If c(v1) = 2, then c(v2) = 1 (if v2 exists). It follows immediately from
Lemma 1 that k ≤ 2. Otherwise, c(v1) = 1, c(v2) = 2, c(v3) = 1 and c(v4) = 3
(if these vertices exist). Next, if v5 exists, then there are again two possibilities
for c(v5) that is, c(v5) = 2 or c(v5) = 1. Thus, repeating the above process and
continuing in this way the result follows. 2

An immediate consequence of Lemma 4 is the following, which we will use
repeatedly henceforth.

Lemma 5. Let F ⊆ S ⊆ T be trees, where F is uniquely 3-χρ-packable, and let c
be any 3-χρ-packing of T . For every u ∈ V (S) and every 3-χρ-packing c′ of S, we
have c′(u) = 3 iff c(u) = 3.

Proof. Let F ⊆ S. Since F is uniquely 3-χρ-packable and c′ a 3-χρ-packing on
S, we have by Lemma 4 that for each v ∈ V (F ) with c(v) = 3, the 3-vertices in
S are those at distance 4i, i ∈ N, from v. Next, let F ⊆ T . Since F is uniquely
3-χρ-packable and c a 3-χρ-packing on T , a similar argument shows that for each
v ∈ V (F ) with c(v) = 3, the 3-vertices in T are those at distance 4i, i ∈ N, from v.
Hence c′(u) = 3 iff c(u) = 3 for all u ∈ V (S). 2

Theorem 6. A tree T is uniquely 3-χρ-packable iff it is obtained from F1, F2 or
F3 by zero or more applications of the operations Oi, i = 1, . . . , 7.



1360 A. Alochukwu, M. Dorfling and E. Jonck

Proof. It follows from the first two parts of Lemma 2 that all trees obtained in
this way are uniquely 3-χρ-packable.

For the converse, let T be a counterexample of minimum order. So, T is uniquely
3-χρ-packable but T cannot be obtained from any smaller uniquely 3-χρ-packable
tree using the operations Oi, i = 1, . . . , 7. Let c : V (T ) → {1, 2, 3} be the 3-χρ-
packing of T .
Claim: T contains F1, F2 or F3 as a subgraph.

Let, according to Lemma 3, x and y be adjacent vertices with colours 2 and 3,
respectively. By Lemma 1, all other neighbours of x have colour 1 and can have
no further neighbours. Moreover, we show that there are at least two vertices of
colour 1 adjacent to x in T . If none, we can recolour x with 1 and so T is not
uniquely 3-χρ-packable. If there exists a unique vertex of colour 1 adjacent to x,
say u1, then we can give u1 colour 2 and x colour 1. This again is a contradiction
to the fact that T is uniquely 3-χρ-packable.

Let P : u1, x, y, u2, u3, . . . , uℓ be a longest path with end-vertex u1. We must
have ℓ ≥ 3, otherwise T is clearly not uniquely 3-χρ-packable.

If y has degree at least 3, then T contains F1. Now assume deg(y) = 2. Since
u2 has colour 1, it follows from Claim 1 that u2 has degree 2. If ℓ < 5, then c is
not unique (interchange the colours of y and u2). Assume therefore that ℓ ≥ 5.

Now if deg(u3) > 2, we have F2 as subgraph, so let deg(u3) = 2. Since c(u4) = 1
we also have deg(u4) = 2. Again, if ℓ = 5, then c is not unique since vertices of P :
u1, x, y, u2, u3, u4, u5 can be coloured 1, 2, 1, 3, 1, 2, 1.

Therefore ℓ ≥ 6. Suppose first that u5 has a 2-neighbour v. If v is adjacent to
one vertex, say v1, then the colours of v and v1 can be interchanged, which implies
that c is not unique. It follows that v has at least two neighbours other than u5

(these have colour 1) and they have no neighbours other than v. If deg(u5) > 2,
T contains F1, and so we let deg(u5) = 2. But then c is not unique since we can
colour vertices u1, x, y, u2, u3, u4, u5, v with 1, 2, 1, 3, 1, 2, 1 and 3, respectively.

Suppose now that all neighbours of u5 have colour 1. Any such neighbour z
must have a 2-neighbour w, otherwise we can change the colour of z to 2 and u5 has
a 2-neighbour as in the argument above. Also, w must have another 1-neighbour,
otherwise the colours of z and w can be switched. Now, if deg(u5) > 2, T contains
F3. Otherwise if deg(u5) = 2, then T is obtained from a smaller uniquely 3-χρ-
packable tree by O7, using Lemma 2(3), which is a contradiction.

Note that “being k-χρ-packable” is an hereditary property of graphs: If a graph
G has the property, so does any subgraph H of G, since for any two vertices u,
v in Xi ∩ V (H), where Xi is an i-packing in G, the following holds: dH(u, v) ≥
dG(u, v) ≥ i+ 1.

Now we prove that any uniquely 3-χρ-packable tree T can only be obtained
from Fi, i = 1, 2 or 3.

Let F be the subtree F1, F2 or F3 of the claim. If T = F we are done, so let
x be a leaf of T that is not in F , and let u be its neighbour. We consider the
following cases.



On uniquely packable trees 1361

Case 1: c(x) = 2.
Since c(x) = 2, we have that c(u) = 1, otherwise we can set c(x) = 1, contradicting
the uniqueness of c. Then u has degree 2 and its neighbour other than x, say w,
must have colour 3.

Let T ′ = T − x. If T ′ is uniquely 3-χρ-packable, the minimality of T is contra-
dicted, since T is obtained from T ′ using O3. So let c′ be a 3-χρ-packing of T ′ that
differs from c on T ′.

We must have c′(u) = 1, otherwise we can extend c′ to T , by setting c′(x) = 1,
to obtain a colouring of T that differs from c. By Lemma 5, c′(w) = 3, so we can
set c′(x) = 2 and again obtain a colouring of T different from c, contradicting the
fact that c is a uniquely 3-χρ-packing of T .
Case 2: c(x) = 3.
Clearly, c(x) = 3 implies that c(u) = 1, otherwise we can set c(x) = 1, contradicting
the uniqueness of c. Then u has degree 2 and its neighbour other than x, say w,
must have colour 2. Let T ′ = T −x. By the minimality of T and the fact that T is
obtained from T ′ using O4, there is a 3-χρ-packing c′ of T ′ that differs from c on
T ′. Again, c′(u) = 1, following a similar argument as in Case 1 above.

From Lemma 5 it follows that we can extend c′ to T by setting c′(x) = 3,
contradicting the uniqueness of c.
Case 3: c(x) = 1. For this case, we have two possibilities for c(u).

� c(u) = 3.
If c(u) = 3, then u must have a 2-neighbour, otherwise we can change c(x)
to 2, contradicting the uniqueness of c. Again, if we let T ′ = T − x, then by
the minimality of T , and the fact that T is obtained from T ′ using O2, there
is a 3-χρ-packing c′ of T ′ that differs from c on T ′. Hence, it follows from
Lemma 5 that any colouring of T ′ can be extended to T by giving x colour 1,
and a contradiction follows as before.

� c(u) = 2.
Let T ′ = T − x and let c′ be a 3-packing colouring of T ′ that differs from c
on T ′. Such a colouring c′ exists by the minimality assumption of T and the
fact that T is obtained from T ′ by applying O1.

Suppose first that the degree of u is at least 4 in T (that is at least 3 in T ′).
Then, c′(u) ̸= 1 by Claim 1, and we can extend c′ to T by letting c′(x) = 1.
This contradicts our assumption that T is uniquely 3-χρ-packable since c and
c′ differ on at least one vertex of T ′. Thus, we now assume that the degree
of u in T is either 2 or 3.

Suppose that deg(u) = 2. Let v be the other neighbour of u. Then c(v) = 1,
otherwise we can swap the colours of x and u. Now, v has degree 2 and its
other neighbour, w say, has colour 3. Let T ′ be obtained from T by removing
those of x, u and v that do not belong to F . (If u ∈ V (F ), then so is v, hence
T ′ is a tree.) Note that T is obtained from T ′ using some combination of O1,
O2 and O3 in most cases. If T ′ = T −{x, u, v}, then T can be obtained from
T ′ by using O5. Consider a 3-χρ-packing c′ of T ′ that differs from c on T ′.
By Lemma 5 we have c′(w) = 3. Those of u and v that belong to F can only



1362 A. Alochukwu, M. Dorfling and E. Jonck

be coloured as by c. Those not belonging to F can be replaced, together with
x, and coloured as by c, contradicting the uniqueness of c.

Therefore, we have deg(u) = 3. Let y and z be the other two neighbours of
u. Suppose first that both have colour 1. One of them, say y, must have
another neighbour w, which can only have colour 3. Since T ′ = T − x and
considering that in any 3-χρ-packing c′ of T ′, we have c′(w) = 3 by Lemma
5, there is only one way to colour u, y and z, hence a contradiction with the
minimality of T follows.

So y, say, has colour 1 and z has colour 3. Examining the graphs Fi, it is
easily checked that u and y cannot belong to F . (Note that y has degree 1.)
We remove x, y and u to obtain T ′, note that T is obtained from T ′ using
O6 and consider a 3-χρ-packing c′ of T ′ that differs from c on T ′.

By Lemma 5, c′(z) = 3. If z has no neighbour w with c′(w) = 2, we are done, as
c′ can be extended to T in the obvious way, so suppose that such a w exists. We
must have c(w) = 1, so, since c′(w) ̸= c(w), we cannot have w ∈ V (F ), because
F is uniquely 3-χρ-packable. If w is a leaf we therefore have the case c(u) = 3,
so suppose w has another neighbour s. Then c′(s) = 1, c(s) = 2 and s is a leaf
(considering c′(z) = 3 and c′(w) = 2). Therefore we have Case 1 and the proof is
complete. 2

3. Monotonocity of the packing colouring. In this section, we consider the
three graphs, F1-F3, described in 2.1, from which all uniquely 3-χρ-packable trees
are constructed and show that their colourings are monotone. In addition, we show
that by iteratively applying any one of the operations O1−O7, we show that there
exists a uniquely 3-χρ-packable tree, Tk, with no monotone χρ-colouring. As a by-
product we obtain sets of uniquely 3-χρ-packable trees with monotone χρ-colouring
and non-monotone χρ-colouring respectively.

Definition 7. Let G be a graph. For a colouring c : V (G) → {1, 2, 3}, and a
colour m, 1 ≤ m ≤ 3, let cm = |{v ∈ V (G) : c(v) = m}|, that is, cm is the
cardinality of the class of vertices, coloured by m. We say that c is monotone if

c1 ≥ c2 ≥ c3.

Proposition 8. ([5]) For any graph G and any m, where m ≤ ⌊χρ(G)/2⌋, there
exists a χρ(G)-colouring c : V (G) → {1, · · · , k} such that cm ≥ cn for all n ≥ 2m.

Note that Proposition 8 above implies that for any graph that is χρ-packable,
cm ≥ c2m and cm ≥ c2m+1 and cm ≥ c2m+2 etc. In particular, for any graph G,
there exists an optimal colouring in which vertices of colour 1 are the most frequent.

Recall the illustrations of the trees F1, F2 and F3 in Figure 1. Observe that for
F1 and F3, c1 > c2 > c3 and for F2, c1 > c2 ≥ c3. Hence, we conclude that Fi’s
are uniquely 3-χρ-packable trees with monotone optimal colouring.

Clearly, by iteratively applying any of the operations Oi defined in 2.1 to our
Fi’s, we have by Lemma 2 that the resulting trees are uniquely 3-χρ-packable.



On uniquely packable trees 1363

We show in the next section that applying some of the operations Oi to the Fi’s,
we obtain uniquely 3-χρ-packable trees, say Tℓ,k and Tk, with monotone and non-
monotone colouring respectively.

We begin by labeling the vertices of Fi’s, as illustrated in Figure 3.

u
2

1

11

y vx

2 31

u
2

1

11

y

z

vx

2 31

13

u
2

1

1

y vx

2 31

13

121

121

Figure 3: The trees F1, F2 and F3 from which all uniquely 3-χρ-packable trees are
constructed.

3.1. Classes of uniquely 3-χρ-packable trees with monotone and non
monotone colouring. We define a τ -path to be a path of length τ . Let Tk,
k ≥ 2, be a class of trees that consists of a 3-path on consecutive vertices u, v, x, y,
each of u and v having two leaves, and there are k paths of length 2 that emerge
from y. The tree Tk was first described in [5].

Figure 4 depicts the family of trees Tk from which a set of uniquely 3-χρ-packable
trees with non-monotone colouring is constructed.



1364 A. Alochukwu, M. Dorfling and E. Jonck

•• •• ••

u

v

x

y •• •• ••

2
1 1

3

1 1

1

2

1
3

1
3

1
3

1
3

Figure 4: The tree Tk from which a set of uniquely 3-χρ-packable trees with non-
monotone colouring is constructed.

Clearly, Tk is obtained from F1 by applying the operations Oi’s for i ∈ {1, 2, 4}
to the vertices. In particular, Tk is obtained from F1 by applying O2 to v once,
applying O1 to y, k-times, and finally applying O4 to the k vertices adjacent to y
respectively.

Similarly, Tk is obtained from F2 by applying the operations Oi’s for i ∈ {1, 2, 4}
to vertices v and y in a manner described below. Apply O2 to v twice, O1 to y,
t-times such that t = k − 2, and finally applying O4 to z and the newly added t
vertices adjacent to y respectively.

By applying similar operation to F3, we obtain another tree, say F ′
3, such that

Tk ⊆ F ′
3. In particular, F ′

3 is obtained by applying O2 to to v twice, applying O1

to y, t′-times such that t′ = k− 1 ≥ 3, and finally applying O4 to the newly added
t′ vertices adjacent to y respectively. Since both Tk and F ′

3 were obtained from
Fi’s by applying the operations O1, O2 and O4, then by Lemma 2.1, we have that
F ′
3 is a uniquely 3-χρ-packable trees but with no monotone colouring.

The following shows that we can obtain a 3-χρ-packable tree with monotone
colouring from Tk by extending the definitions and applying some of the operations
Oi to some vertices of Tk.

For ℓ, k ≥ 2, define Tℓ,k to be a class of trees that consists of a 3-path on
consecutive vertices u, v, x, y, with vertex u having two leaves, and there are ℓ paths
and k paths of length 2 emerging from v and y respectively. Figure 5, shows the
family of trees Tℓ,k from which a set of uniquely 3-χρ-packable trees with monotone
colouring is constructed.



On uniquely packable trees 1365

•• •• ••

•• •• ••

u

v

x

y

•• •• ••

•• •• ••

21 1

3

1 12 2

1
2

1
2

1

2

13 1 3

1
3

1
3

Figure 5: The tree Tℓ,k from which a set of uniquely 3-χρ-packable trees with
monotone colouring is constructed.

Clearly, the tree Tℓ,k is an extension of Tk, which is obtained by applying some
of the operations Oi’s in a manner described below. Apply O2 to v, t-times such
that t = ℓ− 2 ≥ k − 3, O3 to all v′ in N [v]− {u, x}.

Since Tk is a uniquely 3-χρ-packable tree and Tℓ,k is obtained from Tk by ap-
plying the operations Oi’s, we have by Lemma 2.1 that Tℓ,k is also a uniquely
3-χρ-packable tree. Moreover, since Tℓ,k satisfies the conditions of Definition 7, we
conclude that Tℓ,k is a set of uniquely 3-χρ-packable trees with monotone colouring.

4. Conclusion. In this paper we completely characterised all trees T for which
there is only one packing colouring using χρ(T ) = 3 colours. We further inves-
tigated the monotonicity of the packing colouring and obtained sets of uniquely
3-χρ-packable trees with monotone χρ-colouring and non-monotone χρ-colouring
respectively. We now consider the existence of uniquely k-χρ-packable trees for
k > 3 which pose an open question

4.1. Uniquely k-χρ-packable trees. We now consider the existence of uniquely
k-χρ-packable trees for k > 3. In Figure 6 we give examples of uniquely k-χρ-
packable trees for k = 3, . . . , 7. Here, a circle represents a vertex which has suf-
ficiently many unshown leaf neighbours so as to ensure its degree is at least k,
so that the vertex cannot receive colour 1 by Observation 1. Solid vertices have
no hidden neighbours. For instance, T3 represents the graph F1 of the previous
section. We mention that these examples can be adapted to obtain examples of
arbitrary diameter.



1366 A. Alochukwu, M. Dorfling and E. Jonck

2 1 3 2

3 1 2 24 3

31 2 44 5 2 3

2

31 2 45 56 3

2 2

2 4

2

3

31 2 46 75 3

2 2

2 4

3

3

6 5

2

4

1

3

22

2

T3

b

T4

T5

T6

T7

Figure 6: Uniquely k-χρ-packable trees, k = 3, . . . , 7.

These examples were found and verified with the aid of a computer. While a
pattern seems to emerge, the approach fails for k ≥ 8. In fact, we are not sure that
examples exist for all k. We will state this as:

Question 1. Do uniquely k-χρ-packable trees exist for all k?

Proving uniqueness of the given colourings can be done with a straightforward
but tedious case analysis. We give a proof for T6 to illustrate a useful technique
that considerably reduces the amount of work required:

Consider any 6-χρ-packing c of T6. Let F be the subgraph of T6 induced by all
vertices at distance 2 or less from the 6-vertex. Two copies of F are depicted in
Figure 7. There can be at most one 4-vertex, at most one 5-vertex and at most one
6-vertex in F , since F has diameter 4. Consider the sets A1, A2, A3 and B1, B2, B3

indicated in Figure 7. The Ai’s form a partition of V (F ) and each Ai has diameter
at most 2. Therefore there are at most three 2-vertices. The Bi’s similarly partition
V (F ) into sets of diameter at most 3, hence there are at most three 3-vertices.

Since F has nine vertices, it follows that there must be three 2-vertices, one from
each Ai, three 3-vertices, one from each Bi, and one vertex of each of the colours
4, 5 and 6. But B3 has only one element, call it x, so c(x) = 3. Since |A3 − x| = 1,



On uniquely packable trees 1367

the neighbour of x must have colour 2. Now the vertices of F coloured 4,5 and 6
in Figure 6 must have those colours, in some order.

B1A1

A3

B2A2

B3

Figure 7: The subgraph F of T6 used in the uniqueness proof.

2

3

2

3

Figure 8: The subgraph F ′ of T6.

Now consider the subgraph F ′ of T6 induced by all vertices at distance 3 or less
from the 6-vertex, and consider the subsets indicated in Figure 8. Each of the four
sets at the top must contain a 2-vertex, and each of the two sets at the bottom
must contain a 3-vertex. From this the positions of these vertices follow easily.

Considering all of T6 it follows that there must be two 4-vertices and two 5-
vertices, and there is only one way to place these and complete the colouring.

Acknowledgements. Financial support by the DSI-NRF Centre of Excellence in
Mathematical and Statistical Sciences (CoE-MaSS), South Africa is gratefully ac-
knowledged.

References

1. J. Balogh, A. Kostochka, and X. Liu, Packing chromatic number of cubic graphs,
Discrete Math. 341 (2018), 474–483.



1368 A. Alochukwu, M. Dorfling and E. Jonck

2. , Packing chromatic number of subdivisions of cubic graphs, Graphs
Combin. 35 (2019), 513–537.

3. B. Brešar and J. Ferme, An infinite family of subcubic graphs with unbounded
packing chromatic number, Discrete Math. 341 (2018), 2337–2342.

4. B. Brešar, J. Ferme, S. Klavžar, and D.F. Rall, A survey on packing colorings,
Discussiones Mathematicae Graph Theory 40 (2020), 923–970.

5. B. Brešar, S. Klavžar, and D.F. Rall, On the packing chromatic number of
Cartesian products, hexagonal lattice, and trees, Discrete Applied Mathematics 155
(2007), 2303–2311

6. B. Brešar, S. Klavžar, D.F. Rall, and K. Wash, Packing chromatic number,
(1, 1, 2, 2)-colorings, and characterizing the Petersen graph, Aequationes Math. 91
(2017), 169–184.

7. G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, Fifth Edition,
CRC Press, New York, 2011.

8. J. Ekstein, J. Fiala, P. Holub, and B. Lidický, The packing chromatic number
of the square lattice is at least 12, arXiv:1003.2291v1, 2010.

9. J. Ekstein, P. Holub, and O. Togni, The packing coloring of distance graphs
D(k, t), Discrete Appl. Math. 167 (2014), 100–06.

10. J. Fiala and P.A. Golovach, Complexity of the packing coloring problem for trees,
Discrete Applied Mathematics 158 (2010), 771–778.

11. J. Fiala, S. Klavžar, and B. Lidický, The packing chromatic number of infinite
product graphs, European Journal of Combinatorics 30 (2009), 1101–113.

12. A.S. Finbow and D.F. Rall, On the packing chromatic number of some lattices,
Discrete Applied Mathematics 158 (2010), 1224–1228.

13. J. Fresán-Figueroa, D. González-Moreno, and M. Olsen, On the packing
chromatic number of Moore graphs, Discrete Applied Mathematics 289 (2021), 185–
193.

14. W. Goddard, J.M. Harris, S.M. Hedetniemi, S.T. Hedetniemi, and D.F. Rall,
Broadcast chromatic numbers of graphs, Ars Combinatoria 86 (2008), 33–49.

15. P. Holub and R. Soukal, A note on packing chromatic number of the square
lattice, Electronic Journal of Combinatorics, 17 (2010), Article Number N17,
https://doi.org/10.37236/466

16. Z. Shao and A. Vesel, Modeling the packing coloring problem of graphs, Applied
Mathematical Modelling 39(13) (2015), 3588–3599.

17. C. Sloper, Broadcast-coloring in trees, TR 233, University of Bergen, Bergen, 2002.

18. B. Subercaseaux and M.J. Heule, The packing chromatic number of the infinite
square grid is 15, arXiv:2301.09757, 2023.

19. O. Togni, On packing colorings of distance graphs, Discrete Appl. Math. 167 (2014),
280–289.

Received 6 May, 2023 and in revised form 14 December, 2023.