A Novel Algorithm for Adjacent Vertex-Distinguishing Edge Coloring of Large-scale Random Graphs
Zhao Huanping, Zhu Peijin, Jingwen Li, Shi Huojie · Journal of Engineering Science and Technology Review · 2021
Graph coloring is one of the areas in graph theory with high research importance.Adjacent vertex-distinguishing edge coloring is a type of multi-conditional coloring in graph coloring, but existing associated studies lack analysis on constraint conditions.In this study, a novel algorithm was designed to increase the adjacent vertex-distinguishing edge coloring efficiency of large-scale random graphs.Sub-graphs were produced in this work by using a nondestructive segmentation algorithm to reduce the scale of random graphs, and random pre-coloring was performed on the edges of each sub-graph.Iteration was performed step by step in accordance with regulations by searching the conflict set of inaccurate edge coloring until the color met the requirements of the ultimate objective function.Next, the sub-graphs that were colored successfully were combined to realize adjacent vertex-distinguishing edge coloring of large-scale random graphs.Afterward, the accuracy of the adjacent vertex-distinguishing edge chromatic number was proven through theoretical analysis and experimental comparison.Several experiments were also performed on random graphs with less than 4000 vertexes and an edge density smaller than 0.1.Results show that when the number of vertexes is greater than 2000 and the edge density exceeds 0.07, the run time generally rings from 0.9 s to 1.5 s, whereas the run time for other random graphs is between 0.6 and 1.2 s.The algorithm can solve the adjacent vertex-distinguishing edge chromatic number of random graphs effectively, and the time complexity of the algorithm do not exceed O(n 3 ) .The proposed algorithm provides evidence for solving the shortest path of large-scale random graphs.