Graph coloring with cardinality constraints on the neighborhoods

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over tilde(upsilon) of each vertex upsilon, the number of vertices in (N) over tilde(upsilon) boolean AND V-i is (at most) a given integer h(upsilon)(i). The complexity of some variations is discussed according to (N) over tilde(upsilon), which may be the usual neighbors, or the vertices at distance at most 2, or the closed neighborhood of upsilon (upsilon and its neighbors). Polynomially solvable cases are exhibited (in particular when G is a special tree). (C) 2009 Elsevier B.V. All rights reserved.