Maximizing the number of unused colors in the vertex coloring problem
type: Item
instance of: scholarly article
title: Maximizing the number of unused colors in the vertex coloring problem
zbMATH Open document ID: 0809.05047
DOI: 10.1016/0020-0190(94)00113-8
author: Shlomo Lahav
author: Refael Hassin
published in: Information Processing Letters
publication date: 1994-12-08T00:00:00Z
review text: For a graph \(G\) if \(| V(G)|\) colors are available, a coloring of the vertices of \(G\) is always possible. However, for a given noncomplete graph, usually not all of these colors are necessary and the problem considered in this paper is that of maximizing the number of unused colors. An algorithm yielding a coloring of \(G\) of order \(n\) is proposed such that each color class contains at most three vertices and if \(\chi\) and \(\chi'\) denote the size of a coloring of minimum size and the size of the coloring produced by this algorithm, respectively, one has \(n- \chi'\geq {2\over 3} (n-\chi)\), and the bound is tight.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 681758
zbMATH Keywords: vertex coloring
zbMATH Keywords: matching problem
zbMATH Keywords: unused colors
zbMATH Keywords: algorithm
zbMATH Keywords: color class
zbMATH Keywords: bound
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00113-8
OpenAlex ID: W2095314925
cites work: Approximation results for the minimum graph coloring problem
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: On the hardness of approximating minimization problems
Recommended article: Maximizing proper colorings on graphs
Recommended article: Max-coloring of vertex-weighted graphs
Recommended article: On the max coloring problem
Recommended article: On the Max Coloring Problem
Recommended article: Maximising ‐colourings of graphs
Recommended article: Maximum colorful cliques in vertex-colored graphs
Recommended article: Maximum colorful cycles in vertex-colored graphs
Recommended article: Maximizing the number of q -colorings
Recommended article: Maximum number of colors: C-coloring and related problems
Recommended article: On the maximum number of colorings of a graph
description: scientific article; zbMATH DE number 681758