Algorithms for maximum k‐colorings and k‐coverings of transitive graphs
Fǎnicǎ Gavril · Networks · 1987
Abstract Consider a graph G and a positive integer k. The maximum k‐coloring problem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. The maximum k‐covering problem is to find k disjoint cliques covering a maximum number of vertices. The present paper contains polynomial time algorithms for finding maximum k‐colorings and maximum k‐coverings of transitive graphs.