Graph coloring with cardinality constraints on the neighborhoods

Costa, MarieChristine
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. 362369
English
Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph a kcoloring, 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: 38
File downloads: