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

DOI10.1016/J.DAM.2008.06.013MaRDI QIDQ1028481zbMATHOpenAlexFDO

Authors Dominique De Werra, Marc Demange, Bruno Escoffier, Jérôme Monnot, 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 coloringNP-completenessplanar graphsbipartite graphssplit graphsapproximabilityweighted edge coloringweighted node coloring

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• scientific article; zbMATH DE number 1953087
• Sum coloring of bipartite graphs with bounded degree
• scientific article; zbMATH DE number 1947053
• Approximating the max edge-coloring problem

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3513839 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 1953087 (Why is no real title available?)
• scientific article; zbMATH DE number 772747 (Why is no real title available?)
• scientific article; zbMATH DE number 772760 (Why is no real title available?)
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• A coloring problem for weighted graphs
• Algorithms and Computation
• Automata, Languages and Programming
• Batch processing with interval graph compatibilities between tasks
• Difference graphs
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• On the Max Coloring Problem
• Planar Formulae and Their Uses
• Precoloring Extension III: Classes of Perfect Graphs
• Scheduling with incompatible jobs
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• The maximum saving partition problem
• Time slot scheduling of compatible jobs
• Weighted coloring: further complexity and approximability results

Cited in

(24)

• A note on compact and compact circular edge-colorings of graphs
• Cutting Barnette graphs perfectly is hard
• On the max coloring problem
• Bounds and fixed-parameter algorithms for weighted improper coloring
• A note on the Cornaz-Jost transformation to solve the graph coloring problem
• Parameterized complexity of list coloring and max coloring
• Algorithms and Computation
• Improved approximation algorithms for the max edge-coloring problem
• Clique partitioning with value-monotone submodular cost
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
• Saving colors and max coloring: some fixed-parameter tractability results
• Probabilistic graph-coloring in bipartite and split graphs
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Clique clustering yields a PTAS for max-coloring interval graphs
• Max-coloring of vertex-weighted graphs
• No-wait scheduling problems with batching machines
• Dual parameterization of weighted coloring
• Dual parameterization of weighted coloring
• scientific article; zbMATH DE number 1953087 (Why is no real title available?)
• The assignment problem with nearly Monge arrays and incompatible partner indices
• Bounded max-colorings of graphs
• Open shop scheduling with synchronization
• Saving colors and max coloring: some fixed-parameter tractability results
• Approximating the max-edge-coloring problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028481)