Graph coloring with cardinality constraints on the neighborhoods

Marie-Christine Costa, Dominique de Werra, Christophe Picouleau and 
Bernard Ries
november, 2009
Type de publication :
Article (revues avec comité de lecture)
Journal :
Discrete Optimization, vol. 6, 4, pp. 362--369
Résumé :
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 :
    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 },
    volume={6, 4 },