Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation
de Werra, Dominique; Demange, Marc; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2004), Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation, in Fleischer, Rudolf; Trippen, Gerhard, Algorithms and Computation 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings, Springer : Berlin, p. 896-907. http://dx.doi.org/10.1007/978-3-540-30551-4_76
TypeCommunication / Conférence
External document linkhttp://hal.archives-ouvertes.fr/hal-00004074/fr/
Conference title15th International Symposium on Algorithms and Computation (ISAAC'04)
Book titleAlgorithms and Computation 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings
Book authorFleischer, Rudolf; Trippen, Gerhard
Series titleLecture Notes in Computer Science
Number of pages935
MetadataShow full item record
Abstract (EN)We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-complete in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-complete in P8-free bipartite graphs, but polynomial for P5-free bipartite graphs. We next focus ourselves on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-complete, even in the case where the input-graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6 – epsi, for any epsi > 0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.
Subjects / KeywordsGraph coloring; weighted node coloring; weighted edge coloring; approximability; bipartite graphs; split graphs
Showing items related by title and author.
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié
Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009) Article accepté pour publication ou publié