Three-quarter approximation for the number of unused colors in graph coloring
type: Item
instance of: scholarly article
title: Three-quarter approximation for the number of unused colors in graph coloring
zbMATH Open document ID: 0937.05044
DOI: 10.1016/S0020-0255(98)10058-0
author: Wen-Guey Tzeng
author: Gow-Hsing King
published in: Information Sciences
publication date: 2000-06-07T00:00:00Z
review text: Since it is hard to approximate \(\chi(G)\), the minimum number of colors in a graph coloring, the authors consider to approximate the maximum number of unused colors. This approximation is to maximize the ratio \(r_A=(n-A(G))/(n-\chi(G))\), where \(A(G)\) is the number of colors found by a polynomial-time coloring \(A\) when used to graph \(G\). The authors propose a new polynomial algorithm with \(r_A=3/4\), which improves the previous result of 2/3. The key part of the algorithm is to approximate \(n-\phi(G)\) with ratio 3/4 for 4-clique-free graphs, where \(\phi(G)\) is the minimum number of cliques to which the vertices of \(G\) can be partitioned. The algorithm uses a concept similar to the notion of augmenting path in the classical matching problem, however, more complicated.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1384913
zbMATH Keywords: chromatic number
zbMATH Keywords: coloring
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: cliques
zbMATH Keywords: matching
reviewed by: Marek Kubale
MaRDI profile type: Publication
cites work: Approximation results for the minimum graph coloring problem
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Q3684121
cites work: Maximizing the number of unused colors in the vertex coloring problem
cites work: The general maximum matching algorithm of Micali and Vazirani
cites work: On the hardness of approximating minimization problems
cites work: Improving the performance guarantee for approximate graph coloring
cites work: Covering edges by cliques with regard to keyword conflicts and intersection graphs
full work available at URL: s0020-0255(98)10058-0
OpenAlex ID: W2034731049
description: scientific article; zbMATH DE number 1384913