Perfectness and Imperfectness of the kth Power of Lattice Graphs

Abstract

Given a pair of non-negative integers m and n, S(m,n) denotes a square lattice graph with a vertex set {0,1,2,...,m – 1} × {0,1,2,...,n – 1}, where a pair of two vertices is adjacent if and only if the distance is equal to 1. A triangular lattice graph T(m,n) has a vertex set {(xe ₁ + ye ₂) | x ∈ {0,1,2,...,m − 1}, y ∈ {0,1,2,...,n − 1}} where $e_1 = (1,0), e_2 = (1/2, \sqrt{3}/2)$, and an edge set consists of a pair of vertices with unit distance. Let S ^k(m,n) and T ^k(m,n) be the kth power of the graph S(m,n) and T(m,n), respectively. Given an undirected graph G = (V,E) and a non-negative vertex weight function $w : V \longrightarrow Z_+$, a multicoloring of G is an assignment of colors to V such that each vertex v ∈ V admits w(v) colors and every adjacent pair of two vertices does not share a common color.

In this paper, we show necessary and sufficient conditions that [∀ m, theS ^k(m,n) is perfect] and/or [∀ m, T ^k(m,n) is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (S ^k(m,n),w) and (T ^k(m,n),w).