# Graph coloring with cardinality constraints on the neighborhoods

november, 2009

Publication type:

Paper in peer-reviewed journals

Journal:

Discrete Optimization, vol. 6, 4, pp. 362--369

HAL:

Abstract:

Extensions and variations of the basic problem of graph coloring are
introduced. It 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 (v) of each vertex v, the number of vertices in ˜N (v) \ V i
is (at most) a given integer hi
v. The complexity of some variations is
discussed according to ˜N (v) which may be the usual neighbors, or the
vertices at distance at most 2 or the closed neighborhood of v (v and its
neighbors). Polynomially solvable cases are exhibited (in particular when
G is a special tree).

BibTeX:

@article{Cos-DeW-Pic-Rie-2009, author={Marie-Christine Costa and Dominique de Werra and Christophe Picouleau and Bernard Ries }, title={Graph coloring with cardinality constraints on the neighborhoods }, doi={10.1016/j.disopt.2009.04.005 }, journal={Discrete Optimization }, year={2009 }, month={11}, volume={6, 4 }, pages={362--369}, }