Packing chromatic number of square lattice

Abstract

The notion of packing coloring comes from the area of frequency planning in wireless networks, and was introduced by Goddard et al [1], under the name broadcast coloring. Broadcast colouring seems to have been renamed packing colouring in the work in [8].If two vertices of a graph are at distance d and the vertices represent radio stations, and if the radio stations are close enough so that they assign frequencies that interfere with each other, a coloring can be used to reassign non-interfering frequencies to the stations. The United States Federal Communications Commission has come up with many rules and regulation with regards to the assignment of broadcast frequencies to radio stations. Specifically, two radio stations which have received the same broadcast frequency must be located sufficiently far apart so that neither broadcast interferes with the reception of the other.

A function π: V → {1,2,...,k} is packing coloring of order k if π(u) = π(v) means that the distance between u and v is more than π(u). The minimum number of colors with which the vertices of a graph G can be packing colored is called the packing chromatic number, denoted by χρ(G). In this dissertation, we will be investigating the upper bound and the lower bound of the packing chromatic number of graphs, in particular, that of the 2-dimensional infinite square lattice.

Suppose n is an integer n ≥ 1. Define c = 4n. We will also investigate the packing chromatic number of the Cartesian product of C4 and Cc. Since the sub-grid P4 Pc is a sub-graph of the torus C4 Cc, we know that χρ(P4 Pc) ≤ χρ(C4 Cc). Generally speaking, χρ(Pr Pc) ≤ χρ(Cr Cc) for r rows and c columns where r and c are in N, where r, c ≥ 3. The relationship between the packing chromatic numbers of the grid and torus will be remarked on further in the conclusion of this study.