Approximation results for the optimum cost chromatic partition problem

DOI10.1007/3-540-63165-8_226zbMath1401.68353OpenAlexW2281633950MaRDI QIDQ4572001

Klaus Jansen

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_226

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (19)

The \(d\)-precoloring problem for \(k\)-degenerate graphs ⋮ Approximation results for the optimum cost chromatic partition problem ⋮ A note on polynomial algorithm for cost coloring of bipartite graphs with \(\Delta \leq 4\) ⋮ On chromatic sums and distributed resource allocation ⋮ Minimum sum coloring problem: upper bounds for the chromatic strength ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Minimum sum set coloring of trees and line graphs of trees ⋮ On coloring problems with local constraints ⋮ On coloring problems with local constraints ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Minimum sum edge colorings of multicycles ⋮ Minimum sum multicoloring on the edges of trees ⋮ Hard coloring problems in low degree planar bipartite graphs ⋮ Precoloring extension of co-Meyniel graphs ⋮ On the minimum sum coloring of \(P_4\)-sparse graphs ⋮ Sum coloring and interval graphs: A tight upper bound for the minimum number of colors ⋮ Minimum Sum Coloring of P4-sparse graphs ⋮ A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The maximum k-colorable subgraph problem for chordal graphs
• On chain and antichain families of a partially ordered set
• On a graph partition problem with application to VLSI layout
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• Approximation results for the optimum cost chromatic partition problem

This page was built for publication: Approximation results for the optimum cost chromatic partition problem