Packing chromatic number of unitary Cayley graphs of ${\mathbb{Z}}_n$ and algorithmic approaches to it

Abstract

A packing $k$-coloring of a graph $G$ is a partition of $V(G)$ into $k$ disjoint non-empty classes $V_1,\dots ,V_k$, such that if $u,v\in V_i$, $i\in [k]$, $u\ne v$, then the distance between $u$ and $v$ is greater than $i$. The packing chromatic number of $G$ is the smallest integer $k$ which admits a packing $k$-coloring of $G$. In this paper, the packing chromatic number of the unitary Cayley graph of ${\mathbb{Z}}_n$ is computed. Two metaheuristic algorithms for calculating the packing chromatic number are also proposed.