On the packing chromatic numbers of some connected spanning subgraphs of Z3

Abstract

Let G be a graph. A function π : V(G) → 1, 2, ..., k is referred to as a packing colouring of order k, k ∈ Z+, if π(v) = π(u), where u,v ∈ V(G), implies that d(u,v) > π(u). The minimum order of a packing colouring of a graph G is referred to as the packing chromatic number of G, and is denoted by χρ(G). The infinite square lattice, denoted by Z2, is defined as the Cartesian product of Z and Z, that is, Z□Z, where Z is the two-way infinite path. Similarly, the infinite cubic lattice, denoted by Z3, is defined as the Cartesian product of (Z□Z)□Z. In this thesis we consider the following question: What is the minimum proportion of edges that must be removed from Z3 to obtain a connected spanning subgraph for which a finite packing colouring exists?