An Algorithm for Total Coloring of a Simple Graph

Although there are many kinds of formulated or unformulated problems which could solve through graph total coloring, there is no comprehensive algorithm in this case. Total coloring of a simple graph provide a framework for coloring all elements of a simple graph, in which no two adjacent vertices or edges have the same color. In this algorithm, we use the adjacency matrix of an assumed simple graph and determine the connected components with respect to the modified matrix properties. After finding maximum clique, we start graph total coloring from the maximum completed subgraph, determine the coloring list and try to color the graph with minimum cost. The proposed algorithm uses adjacency matrix for decision making which simplify its different steps. On the other hand, the application of famous and simple algorithms such as rank order clustering, may improve its popularity as a solution of related problems. As a result we have a total colored simple graph or a set of connected ones in minimum cost which may be implemented in many cases.

کلیدواژه ها:

Graph Total Coloring. Simple Graph: Connected Component ، Clique ، Rank OrderClustering (ROC)