|
 
|
[CDP09] Graph coloring with cardinality constraints on the neighborhoods
Revue Internationale avec comité de lecture : Journal Discrete Optimization, vol. 6(4), pp. 362-369, 2009, (doi:10.1016/j.disopt.2009.04.005)
motcle:
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).
Equipe:
oc
Collaboration:
LAMSADE
BibTeX
| @article { | |||
| CDP09, | |||
| title | = | "{Graph coloring with cardinality constraints on the neighborhoods}", | |
| author | = | "M.-C. Costa and D. de Werra and C. Picouleau and B. Ries", | |
| journal | = | "Discrete Optimization", | |
| year | = | 2009, | |
| volume | = | 6, | |
| number | = | 4, | |
| pages | = | "362-369", | |
| doi | = | "10.1016/j.disopt.2009.04.005", | |
| } | |||
