How good can a graph be n-colored? : (preprint)
Paul M. B. Vitanyi · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1977
The problem of how "near" we can come to an n-colorine of a given graph is investigated.I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors.In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete.For each graph G, however, colors can be assigrn~d to the vertices in such a way that the number of offending edges is less than or equal to the total number of edges divided by the number of colors.Furthermore, an O(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and pis the number of vertices of the graph (e ~~ p ~ n).A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K in K and m p equicolored graphs in K. p