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) def, = {(xe_1 + ye_2) | x ∈ {0, 1,..., m-1}, y ∈ {0,1,...,n - 1}} where e_1 def, = (1,0), e_2 def, = (1/2, {the square root of}3/2). 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. This paper discusses a necessary and sufficient condition that T_(m, n)(d) is perfect; we show that [(arbitrary)m ∈ Z_+, T_(m, n)(d) is perfect] if and only if d ≥ {the square root of}(n~2 - 3n + 3). Given a non-negative vertex weight vector w ∈ 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 ∈ 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 approximation algorithm for multicoloring (T_(m, n)(d), w). Our algorithm finds a multicoloring which uses at most α(d)ω + O(d~3) colors, where ω denotes the weighted clique number. When d = 1, {the square root of}3, 2, {the square root of}7, 3, the approximation ratio α(d) = (4/3), (5/3), (5/3), (7/4), (7/4), respectively. When d > 1, we showed that α(d) ≤ (1 + 2/({the square root of}3 + (2{the square root of}3-3)/d))) < 1 + 2/{the square root of}3 < 2.155.
展开▼
