论文标题
在$ l $ $的距离距离无限六边形网格的距离
On the Span of $l$ Distance Coloring of Infinite Hexagonal Grid
论文作者
论文摘要
对于图$ g（v，e）$和$ l \ in \ mathbb {n} $，$ l $ dance coloring是颜色$ f：v \ to \ to \ {1，2，\ cdots，\ cdots，n \} $ of $ v $ of $ v $ u \ neq v，\; f（u）\ neq f（v）$当$ d（u，v）\ leq l $。这里$ d（u，v）$是$ u $和$ v $之间的距离，等于连接$ u $和$ g $的最小边数。 $ g $，$λ^{l}（g）$的$ l $距离着色的最低$ n $是$ g $的所有$ n $。蜂窝网络中的一类通道分配问题可以作为常规网格图中的距离图着色问题进行表述。蜂窝网络通常被建模为无限的六边形网格$ t_h $，因此确定$λ^{l}（t_h）$从实际角度具有相关性。 Jacko和Jendrol [讨论Mathematicae Graph Dograph，$ 2005 $]确定了$λ^{l}（t_h）$的确切值，对于任何奇数$ l $，甚至对于$ l \ geq 8 $，它可以推测$λ^{l}（l}（l}（t_h）（t_h）（t_h）（t_h）= \ weft [\ dfrac [\ dfrac] l+\ dfrac {4} {3} \ right） ^2 \ right] $，其中$ [x] $是整数，$ x \ in \ mathbb {r} $和$ x- \ dfrac {1} {1} {1} {2} {2} <[x] \ leq x+leq x+\ dfrac {\ leq x+\ dfrac {1} $} $。对于$ l = 8 $，Sasthi和Subhasis证明了猜想[$ 22 $ nd意大利理论计算机科学会议，$ 2021 $]。在本文中，我们证明了任何$ L \ geq 10 $的猜想。
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\neq v,\; f(u)\neq f(v)$ when $d(u,v) \leq 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$, $λ^{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 $λ^{l}(T_H)$ has relevance from practical point of view. Jacko and Jendrol [Discussiones Mathematicae Graph Theory, $2005$] determined the exact value of $λ^{l}(T_H)$ for any odd $l$ and for even $l \geq 8$, it is conjectured that $λ^{l}(T_H) = \left[ \dfrac{3}{8} \left( \, l+\dfrac{4}{3} \right) ^2 \right]$ where $[x]$ is an integer, $x\in \mathbb{R}$ and $x-\dfrac{1}{2} < [x] \leq x+\dfrac{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 \geq 10$.
