Let P be a subset of 2-dimensional integer lattice points P = {1,2…,m}×{1,2,…, n}⊆Z2. We consider the graph Gp with vertex set P satisfying that two vertices in P are adjacent if and only if Euclidean distance between the pair is less than or equal to √(2). Given a non-negative vertex weight vector ω ∈ ZP+, a multicoloring of (GP, ω) is an assignment of colors to P such that each vertex ν ∈ P admits ω(ν) colors and every adjacent pair of two vertices does not share a common color. We show the NP-completeness of the problem to determine the existence of a multicoloring of (GP, ω) with strictly less than (4/3)ω colors where ω denotes the weight of a maximum weight clique. We also propose an O(mn) time approximation algorithm for multicoloring (GP, ω). Our algorithm finds a multicoloring with at most (4/3)ω + 4 colors. Our algorithm based on the property that when n = 3, we can find a multicoloring of (GP, ω) with ω colors easily, since an undirected graph associated with (GP, ω) becomes a perfect graph.
