Three-quarter approximation for the number of unused colors in graph coloring

DOI10.1016/S0020-0255(98)10058-0zbMath0937.05044OpenAlexW2034731049MaRDI QIDQ1818979

Wen-Guey Tzeng, Gow-Hsing King

Publication date: 7 June 2000

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0255(98)10058-0

zbMATH Keywords

matchingchromatic numberpolynomial algorithmcliquescoloring

Mathematics Subject Classification ID

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

Related Items (3)

Conjugate conflict continuation graphs for multi-layer constrained via minimization ⋮ Diagnosing crosstalk faults in a class of dilated blocking optical multistage interconnection networks ⋮ The maximum saving partition problem

Cites Work

• Unnamed Item
• Unnamed Item
• The general maximum matching algorithm of Micali and Vazirani
• Some simplified NP-complete graph problems
• Approximation results for the minimum graph coloring problem
• Maximizing the number of unused colors in the vertex coloring problem
• Improving the performance guarantee for approximate graph coloring
• 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: Three-quarter approximation for the number of unused colors in graph coloring