
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érenceDate
2004Conference title
30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04)Conference date
2004-06Conference city
Bad HonnefConference country
AllemagneBook title
Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised PapersBook author
Hromkovic, Juraj; Nagl, Manfred; Westfechtel, BernhardPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
3353Published in
Berlin
ISBN
978-3-540-24132-4
Number of pages
404Pages
377-388
Publication identifier
Metadata
Show full item recordAbstract (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 problemRelated items
Showing items related by title and author.
-
Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
-
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
-
de Werra, Dominique; Demange, Marc; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
-
Demange, Marc; de Werra, Dominique; Monnot, Jérôme; Paschos, Vangelis (2002) Communication / Conférence
-
Monnot, Jérôme; Demange, Marc; Paschos, Vangelis (2003) Article accepté pour publication ou publié