Maximizing the number of unused colors in the vertex coloring problem (Q1336741)

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.