On the Span of $l$ Distance Coloring of Infinite Hexagonal Grid

Abstract

For a graph $G(V,E)$ and $l\in \mathbb{N}$, an $l$ distance coloring is a coloring $f:V\to \{1,2,\cdots ,n\}$ of $V$ such that $\forall u,v\in V,u\ne v,f(u)\ne f(v)$ when $d(u,v)\le l$. Here $d(u,v)$ is the distance between $u$ and $v$ and is equal to the minimum number of edges that connect $u$ and $v$ in $G$. The span of $l$ distance coloring of $G$, ${\lambda }^l(G)$, is the minimum $n$ among all $l$ distance coloring of $G$. A class of channel assignment problem in cellular network can be formulated as a distance graph coloring problem in regular grid graphs. The cellular network is often modelled as an infinite hexagonal grid $T_H$, and hence determining ${\lambda }^l(T_H)$ has relevance from practical point of view. Jacko and Jendrol [Discussiones Mathematicae Graph Theory, $2005$] determined the exact value of ${\lambda }^l(T_H)$ for any odd $l$ and for even $l\ge 8$, it is conjectured that ${\lambda }^l(T_H)=\left[\frac{3}{8}{\left(l+\frac{4}{3}\right)}^2\right]$ where $[x]$ is an integer, $x\in \mathbb{R}$ and $x-\frac{1}{2}<[x]\le x+\frac{1}{2}$. For $l=8$, the conjecture has been proved by Sasthi and Subhasis [$22$nd Italian Conference on Theoretical Computer Science, $2021$]. In this paper, we prove the conjecture for any $l\ge 10$.