The $S$-packing coloring of the infinite diagonal grid with $S=(1,6,6,\dots )$

Abstract

For a non-decreasing sequence of positive integers $S=(a_1,a_2,\dots )$, the $S$-packing chromatic number of a graph $G$ is the smallest positive integer $k$ such that the vertices can be colored with $k$ colors, where the distance between any two distinct vertices of color $i$ is greater than $a_i$. In this paper, we show that the $S$-packing chromatic number of the infinite diagonal grid $P_{\infty }⊠P_{\infty }$ with $S=(1,6,6,\dots )$ is $40$. This confirms a conjecture of the first author and Tiyajamorn.

27 pages, 33 figures, submitted