View in EDS

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

Saved in:
Bibliographic Details
Title: On the Span of ℓ Distance Coloring of Infinite Hexagonal Grid.
Authors: Koley, Subhasis1 (AUTHOR) subhasis.koley2@gmail.com, Ghosh, Sasthi C.2 (AUTHOR) sasthi@isical.ac.in
Source: International Journal of Foundations of Computer Science. Nov2024, Vol. 35 Issue 7, p791-813. 23p.
Subjects: Graph coloring, Computer science conferences, Assignment problems (Programming), Graph theory, Regular graphs, Integers
Abstract: 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]
Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract: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]
ISSN:01290541
DOI:10.1142/S012905412350020X