Maximizing the number of unused colors in the vertex coloring problem

DOI10.1016/0020-0190(94)00113-8zbMath0809.05047OpenAlexW2095314925MaRDI QIDQ1336741

Shlomo Lahav, Refael Hassin

Publication date: 8 December 1994

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

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

zbMATH Keywords

algorithmboundvertex coloringmatching problemcolor classunused colors

Mathematics Subject Classification ID

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

Related Items (9)

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems ⋮ Dual parameterization of Weighted Coloring ⋮ Approximating k-set cover and complementary graph coloring ⋮ Approximation algorithms for some vehicle routing problems ⋮ The maximum saving partition problem ⋮ 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

• Approximation results for the minimum graph coloring problem
• On the hardness of approximating minimization problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Maximizing the number of unused colors in the vertex coloring problem