Properties Of Critical R-hued Coloring Graph

Graph coloring problem is a classical NP-hard problem in graph theory,which refers to use the least number of colors to color every vertex in a graph such that every adjacent vertices are colored differently.Many problems in reality can be modeled as graph coloring problem,such as channel allocation in wireless networks,circuit design and nucleic acid sequence design.The r-hued coloring problem studied in this paper comes from the dynamic coloring problem of graphs,which is added neighborhood restriction compared to the classical vertices coloring,that is,the colors used in the neighborhood of any vertex v in the graph is at least min{d(v),r},which r is an arbitrary positive integer.Due to the chromatic number may increase after reducing vertices or edges under r-hued coloring,r-hued coloring problem is also far more complicated than classical vertex coloring,so it is very important to study the criticality of r-hued coloring.Due to the particularity of r-hued coloring,the second chapter of this paper is studied the existence of critical(k,r)-coloring graphs with any positive integer k,r.And this problem are divided into two parts:the existence of(k,r)-coloring graphs of order equal to its r-hued chromatic numbers and the existence of(k,r)-coloring graphs of order greater than its r-hued chromatic numbers.Based on the criticality and construction methods of some special graphs,the existence of these two cases is studied respectively.And we propose an algorithm to construct r-hued critical graph of order equal to r-hued chromatic numbers.Based on the thought of K-divisible graph proposed by Hajos,in the third section of the second chapter,a critical graph construction method of order greater than r-hued chromatic numbers is proposed and proved to be correct.In the third chapter,we study some properties of r-hued critical graphs.Firstly,we study the edge connectivity and vertex connectivity of r-hued critical graphs.By constructing a perfect matching of special bipartite graph,some results about the edge connectivity and vertex connectivity of any(k,r)-critical graph are estimated.Then we study the sufficient and necessary conditions of r-hued critical graphs.By analyzing the local topological properties of the vertices with same color and the vertices with different color,we prove that a graph G of order at least 5 is not(|V(G)|,r)-critical if there is a vertex that is not in 5--cycle and G is not a star,if χr(G)=rΔ(G)+1,then G must be(|V(G)|,r)-critical.In the last of the third chapter,the minimum degree and local properties of(k,r)-critical graphs arc studied.Through interchanging color in coloralternating graphs,we prove the minimum degree of(k,r)-critical graph and the local properties of two adjacent vertices.