Strong Vertex-distinguishing Total Coloring Algorithm for Complete Graphs based on Equitable Coloring
Zhao Huanping, Xue Dangqin, Shi Huojie · Journal of Engineering Science and Technology Review · 2020
Graph coloring has important research significance in graph theory.Strong vertex-distinguishing total coloring is a type of multi-conditional coloring in graph coloring, but existing associated studies lack analysis on constraint conditions.In this study, a new coloring algorithm was designed to increase the coloring efficiency of the strong vertex-distinguishing total coloring of a complete graph.By combining characteristics of complete graphs and strong vertex-distinguishing total coloring, the proposed algorithm decomposed the coloring color numbers into propercolor numbers and overcolor numbers, and the algorithm determined the filling quantity of each color number based on the idea of even coloring.The proposed algorithm implemented regular stepwise iteration by searching abnormal color sets on the edge coloring matrix until the constraint condition was achieved.The accuracy of the approach was proven by theoretical analysis and experimental comparison.The multiple experiments on 14-64 orders of complete graphs indicate that the 16-, 32-, and 64-order complete graphs require total coloring combination of overcolor numbers; this process generally needs 0.6-0.7 s.By contrast, the operation times for other orders of complete graphs are generally in the range 0.3-0.4s.The proposed algorithm can effectively calculate the strong vertex-distinguishing total chromatic number of the complete graph with a fixed vertex number, and its time complexity is lower than .These findings can provide important references in studying adjacent vertex-distinguishing total coloring and vertex-distinguishing total coloring.