关键词: 图, 正常均匀全染色, 均匀全色数

Abstract:

The research on the equitable total coloring is limited to some special graphs such as complete-graph and join-graph. For the normal equitable total coloring of the simple connected graph, there is not any feasible method in the published paper. In order to research the equitable total coloring of the normal graph, a new heuristic intelligent algorithm was proposed according to four constraint rules including vertex constraint rule, edge constraint rule, vertex-edge constraint rule and equitable constraint rule of the equitable total coloring. First, four sub-functions and one total function were ascertained. Second, by using the dyeing matrix and complementary matrix in each sub-function, the iterative exchange did not stop until each sub-function value was zero, that meant the subgoal-coloring was completed. If each sub-function value was 0, the total function value was 0, which meant coloring was successful. The experimental results show that the proposed algorithm can generate all of the simple connected graphs in which the number of vertices is no more than 8, and it can achieve the corresponding coloring, and then obtains the equitable total chromatic number. Also when any positive integer k is not less than 3 and not more than 9, random graph G has k-equitable total coloring. At the same time, the proposed algorithm chooses 72 graphs whose vertex number is between 20 and 400, and draws the diagram about the vertex number, edge number and color number according to the equitable total coloring results.

Key words: graph, normal equitable total coloring, equitable total chromatic number