Graph coloring with cardinality constraints on the neighborhoods
Ries, Bernard; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine (2009), Graph coloring with cardinality constraints on the neighborhoods, Discrete Optimization, 6, 4, p. 362-369. http://dx.doi.org/10.1016/j.disopt.2009.04.005
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Optimization
MetadataShow full item record
Abstract (EN)Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V1,…,Vk of the vertex set of G such that, for some specified neighborhood View the MathML source of each vertex v, the number of vertices in View the MathML source is (at most) a given integer View the MathML source. The complexity of some variations is discussed according to View the MathML source, 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).
Subjects / KeywordsCardinality constrained colorings; Tree; Bipartite graph; Vertex coloring
Showing items related by title and author.
Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2006) Communication / Conférence
Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2007) Communication / Conférence
Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2007) Communication / Conférence