Graph coloring with cardinality constraints on the neighborhoods
-
Costa, Marie-Christine
Conservatoire des Arts et Métiers, Paris, France
-
de Werra, Dominique
EPFL, Lausanne, Switzerland
-
Picouleau, Christophe
Conservatoire des Arts et Métiers, Paris, France
-
Ries, Bernard
EPFL, Lausanne, Switzerland
Show more…
Published in:
- discrete Optimization. - 2009, vol. 6, no. 4, p. 362-369
English
Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph a k-coloring, i.e., a partition (V_1,\cdots,V_k) of the vertex set of G such that, for some specified neighborhood \tilde|{N}(v) of each vertex v, the number of vertices in \tilde|{N}(v)\cap V_i is (at most) a given integer h_i^v. The complexity of some variations is discussed according to \tilde|{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 is a special tree).
-
Faculty
- Faculté des sciences économiques et sociales et du management
-
Department
- Département d'informatique
-
Language
-
-
Classification
-
Computer science and technology
-
License
-
License undefined
-
Identifiers
-
-
Persistent URL
-
https://folia.unifr.ch/unifr/documents/307887
Statistics
Document views: 45
File downloads: