Costa, Marie-Christine de Werra, Dominique Picouleau, Christophe Ries, Bernard 2009 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). application/pdf https://folia.unifr.ch/global/documents/307887 https://folia.unifr.ch/documents/307887/files/neighborhood.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.disopt.2009.04.005 info:eu-repo/semantics/openAccess License undefined discrete Optimization. - 2009, vol. 6, no. 4, p. 362-369 Vertex coloring Bipartite graph Tree Cardinality constrained colorings info:eu-repo/classification/udc/004 Graph coloring with cardinality constraints on the neighborhoods http://purl.org/coar/resource_type/c_6501