Thumbnail

The hypocoloring problem: complexity and approximability results when the chromatic number is small

de Werra, Dominique; Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (2004), The hypocoloring problem: complexity and approximability results when the chromatic number is small, in Hromkovic, Juraj; Nagl, Manfred; Westfechtel, Bernhard, Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Springer : Berlin, p. 377-388. http://dx.doi.org/10.1007/978-3-540-30559-0_32

View/Open
Type
Communication / Conférence
Date
2004
Conference title
30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04)
Conference date
2004-06
Conference city
Bad Honnef
Conference country
Allemagne
Book title
Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers
Book author
Hromkovic, Juraj; Nagl, Manfred; Westfechtel, Bernhard
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
3353
Published in
Berlin
ISBN
978-3-540-24132-4
Number of pages
404
Pages
377-388
Publication identifier
Metadata
Show full item record
Author(s)
de Werra, Dominique
Demange, Marc
Monnot, Jérôme cc
Paschos, Vangelis
Abstract (EN)
We consider a weighted version of the subcoloring problem that we call the hypocoloring problem: given a weighted graph G=(V,E;w) where w(v)S=(S1,¼,Sk)=(S1Sk) of the node set of G into hypostable sets and minimizing max{åv Î Kw(v)| K Î S}maxvKw(v) KS . Properties of hypocolorings are stated; complexity and approximability results are presented in some graph classes. The associated decision problem is shown to be NP-complete for bipartite graphs and triangle-free planar graphs with maximum degree 3. Polynomial algorithms are given for graphs with maximum degree 2 and for trees with maximum degree Delta.
Subjects / Keywords
Algorithms; Approximability; Complexity; Weighted graphs; Subcoloring problem