On the Span of ℓ Distance Coloring of Infinite Hexagonal Grid.

For a graph G (V , E) and ℓ ∈ ℕ , an ℓ distance coloring is a coloring f : V → { 1 , 2 , ... , t } of V with t colors such that ∀ u , v ∈ V , u ≠ v , f (u) ≠ f (v) when d (u , v) ≤ ℓ. 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 ℓ distance coloring of G , χ ℓ (G) , is the minimum t among all ℓ 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 H , and hence determining χ ℓ (H) has relevance from practical point of view. Jacko and Jendrol [Discussiones Mathematicae Graph Theory, 2005] determined the exact value of χ ℓ (H) for any odd ℓ and for even ℓ ≥ 8 , it is conjectured that χ ℓ (H) = 3 8 (ℓ + 4 3) 2 where [ x ] is an integer, x ∈ ℝ and x − 1 2 < [ x ] ≤ x + 1 2 . For ℓ = 8 , the conjecture has been proved by Ghosh and Koley [ 2 2 nd Italian Conference on Theoretical Computer Science, 2021]. In this paper, we prove the conjecture for any even ℓ ≥ 1 0. [ABSTRACT FROM AUTHOR]