The Research Of Graph Weak Coloring Algorithm Based On Spectral Graph Theory

The elementary graph weak coloring problem is the transition to total coloring problem.It is pretty contrary to vertex-distinguishing coloring on the perspective of methodology. Inweak coloring, what should be study is the combination of the coloring criteria. The researchof coloring algorithm also begins with the research on kinds of fundamental graph coloringproblems, for instance, sequential algorithm, bionic algorithm and some other heuristics,some of which are popular in engineering applications. And the spectra-based algorithms area variety of fairly particular way. It is incomparable for spectra-based algorithms with somepowerful performance heuristics or exact ones, nevertheless. for some study of the algorithmperformance evaluation, it’s still attractive and significant.Nowadays, there’re some literatures which classify clique, bisection, coloring etc intograph partition category. Hence, this paper sets up the hypothesis that there’s always onekind of vertex relation which generates graph coloring by spectra clustering. Thus, we willshow a step-by-step process from VCP to weak coloring issue, and find out the relevanceamong coloring criteria.The synopsis of paper is organized as follows.(1) Firstly, the paper sums up existing theories and notions to divide coloring criteria intotwo classes: the first coloring criteria and the second coloring criteria, and lead to weakcoloring problem; After that, review degree-based and spectra-based algorithms, discuss thedifference and conclude the common properties of MostNeg and Alon. And make you knowthat coloring algorithms include some other techniques besides combinational optimizationprocedure by some coloring strategies intro, at last.(2) Here, the paper naturally draws the attention from spectra coloring to spectraclustering. We will introduce similarity matrices, the Laplacian, the mechanism, and somedetails used for graph coloring under the scope of spectra cluster. According to the similaritymentioned in spectra cluster, the paper brings in vertex similarity, which belongs to thenetwork research, to apply it to give a coloring partition by clustering.(3) In the end, the work of this thesis is to design experiments to investigate coloringcriteria. Vertex coloring experiments gain two spectra-based algorithms, a ratiocut coloringbased on Jaccard index and a normalized cut based on adjacency. Both vertices relation andthe Laplacian affects the coloring results, this standpoint is verified simply by abovealgorithms and is differently from the previous one, which only concerns the Laplacian. Thefollowing edge coloring and weak coloring experiments are implemented via the conversionmodel. We use a direct conversion model to convert three kinds of relations includingadjacency of vertices, adjacency of edges and incidence between vertex and edge into a vertex coloring problem, measure the affection of the conversion and obtain the conclusionthat the three types of relations are heterogeneous in spectra-based coloring. This conclusionis always neglected in degree-based coloring and some others.