图的色数的一个上界

An Upper Bound on the Chromatic Number of Graph

本文给出了图的色数的一个新上界,它改进了文献[2]中定理1.8的结论.

Let G be not a complete graph,and let the independence number of G be β_0.Let■ have p vertices and n edges,and let degree sequece of■ be (d_1,d_2,…,d_p),thenχ(G)≤p-max{{(n^2)/(∑d_i^2—n),β_0-1}.