Perfectness and imperfectness of unit disk graphs on triangular lattice points

Given a finite set of 2-dimensional points P ⊆ R 2 and a positive real d , a unit disk graph, denoted by ( P , d ) , is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d . 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. { ( x e 1 + y e 2 ) ∣ x ∈ { 0 , 1 , … , m − 1 } , y ∈ { 0 , 1 , … , n − 1 } } where e 1 = def. ( 1 , 0 ) , e 2 = def. ( 1 / 2 , 3 / 2 ) . Let T m , n ( d ) be a unit disk graph defined on a vertex set P ( m , n ) and a positive real d . Let T m , n k be the k th power of T m , n ( 1 ) . s paper, we show necessary and sufficient conditions that [ ∀ m , T m , n ( d ) is perfect] and/or [ ∀ m , T m , n k is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring ( T m , n ( d ) , w ) and ( T m , n k , w ) .