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.

Published
2010-03-15
Article Number
N17