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

Wen-Guey Tzeng*, Gow Hsing King

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


The graph coloring problem is to color vertices of a graph so that no adjacent vertices are of the same color. The problem is difficult not only in finding the optimal solution, but also in approximation. Since it is hard to approximate the minimum number of colors, we consider to approximate the maximum number of unused colors. This approximation is based on saving colors with respect to the most naive coloring method, which colors each vertex with a different color. In this paper we propose a polynomial-time graph coloring algorithm with approximation ratio 3/4 for the maximum number of unused colors, which improves the previous result 2/3.

Original languageEnglish
Pages (from-to)105-126
Number of pages22
JournalInformation Sciences
Issue number1-4
StatePublished - Mar 1999


  • Approximation
  • Graph coloring

Fingerprint Dive into the research topics of 'Three-quarter approximation for the number of unused colors in graph coloring'. Together they form a unique fingerprint.

Cite this