On the K-Coloring Problem

Abstract

A fixed k-coloring problem is introduced and dealt with by efficient heuristic algorithms. It is shown that the problem can be transformed into the graph partitioning problem. Initial coloring and improving methods are proposed for problems with and without the size restriction. Algorithms Move, LEE and OEE are developed by modifying the Kernighan -Lin*s two way uniform partitioning procedure. The use of global information in the selection of the node and the color set made the proposed algorithms superior to the existing method. The computational result also shows that the superiority does not sacrifice the time demand of the proposed algorithms.