一类特殊图的顶点染色及其猜想的证明

Proof of a Conjecture of A Class of Vertex Coloring of Special Graphs

通过研究一类特殊图的顶点染色,得到了以下结果:给出了S=p-3且p∈{4,5,6},图G的顶点染色数;证明了︱S︱>p2且︱S︱=p-3的图G不存在第p-m类图,m≥7且m是正整数;证明了︱S︱=p-3时,χ(G)≤4θ(G)+θ2(G)-1;进一步证明了猜想χ(G)≤4θ(G)+θ2(G)-1是正确的;为今后研究该猜想和图的顶点染色提供一些思想方法.

Throughout the study on a class of vertex coloring of special graphs,this paper gives the following results：（ 1） Give vertex coloring number of graph G, ︱S︱ =p-3and p∈ {4,5,6}.（ 2） Prove that graph G of S 〉p/2and︱S ︱= p-3 has no the p-m class of graph,m ≥7 and m is positive integer.（ 3） Prove that χ（ G） ≤4θ（ G） ＋θ2（ G）-1,when ︱S ︱=p-3.All kinds of vertex coloring number of graph G when S = p-3are given from these results above,and further it is proven that the conjecture χ（ G） ≤4θ（ G） ＋ θ2（ G）-1 is right.,which provide some thoughts and methods for further study on this conjecture and the graph vertex coloring.