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 journalArticle

6 Scopus citations

Abstract

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
Volume114
Issue number1-4
DOIs
StatePublished - 1 Jan 1999

Keywords

  • 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