Perfectness and Multicoloring of Unit Disk Graphs on Triangular Lattice Points (Theoretical Computer Science and its Applications)
Yuichiro Miyamoto, Tomomi Matsui · Institutional Repositories DataBase (IRDB) · 2005
Given a pair of non-negative integers $m$ and $n$ , $P(m, n)$ denotes a subset of 2-dimensional triangular lattice points defined by $P (m, n)Let $T_{m,n}(d)$ be an undirected graph defined on vertex set $P(m, n)$ satisfying that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to $d$ .In this PaPer, we discuss a necessary and sufficient condition that $T_{m,n}(d)$ is perfect.More precisely, we show that [ $\forall m\in \mathrm{Z}_{+}$ , $T_{m,n}(d)$ is perfect ] if and only if $d\geq\sqrt{n^{2}-3n+3}$ .Given a non-negative vertex weight vector $w\in \mathrm{z}_{+}^{P(m,n)}$ , a multicoloring of $(T_{m,n}(d), w)$ is an assignment of colors to $P(m,n)$ such that each vertex $v\in P(m, n)$ admits $w(v)$ colors and every adjacent pair of two vertices does not share a common color.We also give an efficient algorithm for multicoloring $(T_{m,n}(d), w)$ when $P(m, n)$ is perfect.In general case, our results on the perfectness of $P(m, n)$ implies a polynomial time ap- proximation algorithm for multicoloring $(T_{m,n}(d), w)$ .Our algorithm finds a multicoloring which uses at most $\alpha(d)\omega+\mathrm{O}(d^{3})$ colors, where $\omega$ denotes the weighted clique number.When $d=1$ , $\sqrt{3},2$ , $\sqrt{7},3$ , the approximation ratio $\alpha(d)=(4/3)$ , (5/3), (5/3), (7/4), (7/4), respectively.When $d>1$ , we showed that $\alpha(d)\leq(1+\frac{2}{\sqrt{3}+_{H}^{\underline{2\sqrt}\underline{-3}}})$ .We also showed the $\mathrm{N}\mathrm{P}$ -compteteness of the problem to determine the existence of a multicoloring of $(T_{m,n}(d), w)$ with strictly less than (4/3)cJ colors.