A vertex-composite graph is a graph that can have unequal chromaticities on its vertices. Vertex-composite graph coloring or composite graph coloring involves coloring each vertex of a composite graph with consecutive colors according to the vertex's chromaticity with no two vertices adjacent to one another having the same color(s).
New heuristic algorithms including the use of the saturation degree method have been developed in this research. All eleven heuristic algorithms including Clementson and Elphick algorithms were then tested using random composite graphs with five different chromaticity distributions. The best algorithm which uses the least average colors from the experiment is the MLF1I algorithm follow very closely by the MLF2I algorithm.
Four applications, Timetabling, Job Shop Scheduling, CPU Scheduling and Network Assignment Problem, have been formulated as composite graph coloring problems and solved using heuristic composite graph coloring algorithms.
Yek, Stephen Hong Seng and Gillett, Billy E., "Composite Graph Coloring Algorithms and Applications" (1988). Computer Science Technical Reports. 91.
© 1988 University of Missouri--Rolla, All rights reserved.