Novel Encoding Model for Asymptotically Greater Compactness
Bernardo Subercaseaux, Marijn J.H. Heule
Signals and Telecommunication Journal, Vol. 14, No. 1, 2025.
DOI: https://doi.org/10.6025/stj/2025/14/1/17-34
Link: https://www.dline.info/stj/fulltext/v14n1/stjv14n1_3.pdf
Abstract:
A packing k-coloring for a graph G = (V, E) is defined as a function that assigns colors from the set {1, ..., k} to
the vertices in V. This assignment must ensure that any two vertices u and v that share the same color c are
separated by a distance greater than c within the graph G. One of the key challenges in the area of packing

colorings is to ascertain the packing chromatic number of the infinite square grid. Prior research has estab-
lished that this number lies between 13 and 15. Our study enhances the lower limit to 14. Additionally, we

introduce a novel encoding method that offers asymptotically greater compactness compared to those
previously employed.