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

摘要： 邻点可区别[VI]-均匀全染色是指图中任意两条相邻边分配不同的颜色，且任意两个色类（点或边）的颜色个数最大相差为1，同时确保相邻顶点的色集合不同，其所用的最少颜色数称为图的邻点可区别[VI]-均匀全色数。提出了一种针对随机图的邻点可区别[VI]-均匀全染色算法，该算法依据染色条件设计了三个子目标函数和一个总目标函数，并依据交换规则逐步迭代寻优，直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤，并进行了大量的测试和分析，实验结果表明，该算法可以高效地求出给定顶点数的图的最小邻点可区别[VI]-均匀全色数。

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