Graph coloring with cardinality constraints on the neighborhoods

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).
Type de document :
Article dans une revue
Discrete Optimization, Elsevier, 2009, 6 (4), pp.362--369. 〈10.1016/j.disopt.2009.04.005〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00975361
Contributeur : Aurélien Arnoux <>
Soumis le : mardi 8 avril 2014 - 14:49:11
Dernière modification le : mercredi 6 décembre 2017 - 16:46:01

Lien texte intégral

Identifiants

Collections

Citation

Marie-Christine Costa, Dominique De Werra, Christophe Picouleau, Bernard Ries. Graph coloring with cardinality constraints on the neighborhoods. Discrete Optimization, Elsevier, 2009, 6 (4), pp.362--369. 〈10.1016/j.disopt.2009.04.005〉. 〈hal-00975361〉

Partager

Métriques

Consultations de la notice

93