Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

DOI10.1016/J.DAM.2008.06.013zbMath1173.05325OpenAlexW2163111788MaRDI QIDQ1028481

Marc Demange, Bruno Escoffier, Jérôme Monnot, Dominique de Werra, Vangelis Th. Paschos

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.06.013

zbMATH Keywords

graph coloringplanar graphsNP-completenessbipartite graphssplit graphsapproximabilityweighted edge coloringweighted node coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ The assignment problem with nearly Monge arrays and incompatible partner indices ⋮ No-Wait Scheduling Problems with Batching Machines ⋮ Improved approximation algorithms for the max edge-coloring problem ⋮ Open shop scheduling with synchronization ⋮ A note on the Cornaz-Jost transformation to solve the graph coloring problem ⋮ Bounded max-colorings of graphs ⋮ Dual parameterization of Weighted Coloring ⋮ Cutting Barnette graphs perfectly is hard ⋮ Clique Clustering Yields a PTAS for max-Coloring Interval Graphs ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ On the max coloring problem ⋮ Approximating the max-edge-coloring problem ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Ruling out FPT algorithms for weighted coloring on forests ⋮ Max-coloring of vertex-weighted graphs ⋮ Dual parameterization of weighted coloring ⋮ Clique partitioning with value-monotone submodular cost ⋮ Parameterized complexity of list coloring and max coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A coloring problem for weighted graphs
• Time slot scheduling of compatible jobs
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Weighted coloring: further complexity and approximability results
• Scheduling with incompatible jobs
• The maximum saving partition problem
• Batch processing with interval graph compatibilities between tasks
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• Planar Formulae and Their Uses
• Precoloring Extension III: Classes of Perfect Graphs
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• On the Max Coloring Problem
• Algorithms and Computation
• Automata, Languages and Programming
• Difference graphs

This page was built for publication: Weighted coloring on planar, bipartite and split graphs: Complexity and approximation