Weighted coloring on planar, bipartite and split graphs: complexity and approximation
SujetGraph coloring; Weighted node coloring; Weighted edge coloring; Approximability; NP-completeness; Planar graphs; Bipartite graphs; Split graphs
Journal issueDiscrete Applied Mathematics
MetadataShow full item record
de Werra, Dominique
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-hard 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-hard in P8-free bipartite graphs, but polynomial for P5-free bipartite graphs. We next focus 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-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>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.
Showing items related by title, author, creator and subject.
On the Intersection Graphs of Orthogonal Line Segments in the Plane: Characterizations of Some Subclasses of Chordal Graphs Golumbic, Martin Charles; Ries, Bernard (2013) Article accepté pour publication ou publié
Boutillier, Cédric; Cimasoni, David; de Tilière, Béatrice (2019) Document de travail / Working paper
Paschos, Vangelis; Escoffier, Bruno; Monnot, Jérôme (2006) Article accepté pour publication ou publié