Approximation results for the minimum graph coloring problem

DOI10.1016/0020-0190(94)90039-6zbMath0806.68085OpenAlexW1978711446WikidataQ127981335 ScholiaQ127981335MaRDI QIDQ1321829

Marc Demange, Pascal Grisoni, Vangelis Th. Paschos

Publication date: 13 February 1995

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90039-6

zbMATH Keywords

polynomial time approximation algorithmdifferential approximation ratiominimum vertex coloring problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

Differential approximation algorithm of FSMVRP ⋮ Maximizing the number of unused colors in the vertex coloring problem ⋮ A better differential approximation ratio for symmetric TSP ⋮ Dual parameterization of Weighted Coloring ⋮ Approximating k-set cover and complementary graph coloring ⋮ New differential approximation algorithm for \(k\)-customer vehicle routing problem ⋮ The maximum saving partition problem ⋮ Probabilistic graph-coloring in bipartite and split graphs ⋮ Three-quarter approximation for the number of unused colors in graph coloring ⋮ Differential approximation algorithms for some combinatorial optimization problems ⋮ Dual parameterization of weighted coloring

Cites Work

• Unnamed Item
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• On the hardness of approximating minimization problems

This page was built for publication: Approximation results for the minimum graph coloring problem