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

DOI10.1016/J.DAM.2008.06.013zbMATH Open1173.05325OpenAlexW2163111788MaRDI QIDQ1028481FDOQ1028481

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

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

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)

Cites Work

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

Cited In (24)

• A note on compact and compact circular edge-colorings of graphs
• On the max coloring problem
• Clique partitioning with value-monotone submodular cost
• Cutting Barnette graphs perfectly is hard
• Dual parameterization of Weighted Coloring
• Saving colors and max coloring: some fixed-parameter tractability results
• Clique clustering yields a PTAS for max-coloring interval graphs
• No-wait scheduling problems with batching machines
• A note on the Cornaz-Jost transformation to solve the graph coloring problem
• Probabilistic graph-coloring in bipartite and split graphs
• Bounds and fixed-parameter algorithms for weighted improper coloring
• Dual parameterization of weighted coloring
• Open shop scheduling with synchronization
• Max-coloring of vertex-weighted graphs
• Title not available (Why is that?)
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• The assignment problem with nearly Monge arrays and incompatible partner indices
• Bounded max-colorings of graphs
• Ruling out FPT algorithms for weighted coloring on forests
• Parameterized complexity of list coloring and max coloring
• Approximating the max-edge-coloring problem
• Improved approximation algorithms for the max edge-coloring problem
• Saving colors and max coloring: some fixed-parameter tractability results
• Algorithms and Computation

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)