A new method to find out the chromatic partition of a symmetric graph
Pradip K. Srimani, Bhabani P. Sinha, ARUN K. CHOUDHURY · International Journal of Systems Science · 1978
In this paper an algorithm to find out the chromatic partition of a symmetric graph is described. The algorithm is developed in two stages. In the first stage, all possible maximal independent sets of vertices of the graph ore determined starting from adjacency matrix description of the given graph. Several important results are arrived at about the lower bound on the chromatic number of the graph. Lastly, in the second phase of the algorithm, a minimal cover of the vertices with the maximal independent seta is enumerated by introducing the classical concept of prime implicant covering to obtain the desired chromatic partition of the graph. The proposed algorithm is simple and straightforward and may be programmed on a general purpose digital computer.