关键词: 随机图, 正常均匀全染色, 均匀全色数, 邻点可区别[VI]-均匀全染色

Abstract: The adjacent vertex-distinguishing [VI]-equitable total coloring of graph[G]is that adjacent edges of a graph have different color , the sizes of its color classes（vertex or edge） differ by at most one, and no two adjacent distinct vertices have the same color sets, the minimum number of used colors is called the adjacent vertex distinguishing [VI]-equitable total chromatic number. In this paper, a heuristic algorithm is presented for the adjacent vertex distinguishing [VI]-equitable total coloring of random graphs, which has designed three objective functions and one main function by the constraints, with exchange rules to find the optimum solution, the iterative exchange hasn’t finished until the coloring results satisfy the requirements of main function. At the same time, this paper gives the detailed algorithm steps and the conducted massive testing and analysis. The experimental results show that this algorithm can find the minimum adjacent vertex distinguishing [VI]-equitable total chromatic number which the vertices have given efficiently.

Key words: random graph, normal equitable total coloring, equitable total chromatic number, adjacent vertex distinguishing [VI]-equitable total coloring