与图的顶点染色数有关的几个问题

Several problems related to the vertex coloring number of graphs

设c(G)是无向简单图G(V,E)的顶点染色数,证明了:若︱S︱>p/2且︱S︱=p-m,则图G不存在第p-q类图,其中:q≥2m+1,m≥3且m∈Z^+;若︱S︱=p-4,则小x(G)≤p-3;若︱S︱=p-4,则x(G)≤4■(G)+■2(G)-1.

Let c（G） to be vertex coloring number of undirected simple graph G（V, E）.Proved that if ︱S︱p/2 and︱S︱=p-m,then there is no the p -q class graph in graph G,where q≥2m＋1,m≥3 and m∈Z-＋,if ︱S︱=p-4,then x（G）≤p-3;If ︱S︱=p-4,then x（G）≤4θ（G）＋θ2（G）-1.