Lambda-Coloring of Regular Tiling

(Extended Abstract)

Consider the following coloring problem:

An L(h,k)-coloring of a graph G is a function f from the node set V(G) to the set of all nonnegative integers such that

1. |f(x)-f(y)| <= h if d(x,y)=1 and

2. |f(x)-f(y)| <= k if d(x,y)=2.

The L(h,k)-number of G, denoted by lambda{h,k}(G), is the smallest number of colors necessary to L(h,k)-color G.

In this paper we focus on the problem of L(h,1)-coloring a regular tiling, when h assume values 0,1,2. Namely, we prove the polinomiality of the problem showing that Delta +2^h - 1 colors are necessary and sufficient to give an L(h,1)-coloring, 0 <= h <= 2 , to a regular tiling of degree Delta.

PS Files

Conference Version