A Note on Packing Chromatic Number of the Square Lattice

Roman Soukal, Přemysl Holub

Abstract


The concept of a packing colouring is related to a frequency assignment problem. The packing chromatic number $\chi_p(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set $V (G)$ can be partitioned into disjoint classes $X_1, \dots, X_k$, where vertices in $X_i$ have pairwise distance greater than $i$. In this note we improve the upper bound on the packing chromatic number of the square lattice.


Full Text: PDF