Sách A note on packing chromatic number of the square lattice

1 Introduction
In this paper we consider only simple undirected graphs. We use [1] for terminology and
notation not defined here. Let distG(x, y) denote the distance between vertices x and
y in G. The Cartesian product GH of graphs G and H is the graph with vertex set
V (G) × V (H), where vertices (x, y) and (x
′
, y
′
) are adjacent whenever xx
′
∈ E(G) and
y = y
′
, or x = x
′
and yy
′
∈ E(H). For two infinite paths P1, P2, the Cartesian product
P1P2 is usually called the (infinite) square lattice.
The concept of the packing colouring comes from the area of frequency planning in
wireless networks, and was introduced by Goddard et al. in [3] under the name broadcast
colouring. The packing chromatic number of a graph G, denoted by χp(G), is the smallest
integer k such that V (G) can be partitioned into k disjoint sets X1, . , Xk, where for
each pair of vertices x, y ∈ Xi distG(x, y) > i, for every i = 1, . , k. In other words,
vertices with the same colour i are pairwise at distance greater than i.