Perfectness and imperfectness of unit disk graphs on triangular lattice points

Given a finite set of 2-dimensional points P⊆R2P⊆R2 and a positive real dd, a unit disk graph, denoted by (P,d)(P,d), is an undirected graph with vertex set PP such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to dd. Given a pair of non-negative integers mm and nn, P(m,n)P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by P(m,n)=def.{(xe1+ye2)∣x∈{0,1,…,m−1},y∈{0,1,…,n−1}} where e1=def.(1,0),e2=def.(1/2,3/2). Let Tm,n(d)Tm,n(d) be a unit disk graph defined on a vertex set P(m,n)P(m,n) and a positive real dd. Let Tm,nk be the kkth power of Tm,n(1)Tm,n(1).In this paper, we show necessary and sufficient conditions that [∀m,Tm,n(d) is perfect] and/or [∀m,Tm,nk is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (Tm,n(d),w)(Tm,n(d),w) and (Tm,nk,w).