色临界图的最大度与色数的一个关系式

One Inequality about the Relation between the Maximum Degree and Chromatic Number of Colour-Critical Graphs

研究了一类简单图G的色数x(G)与最大度△(G)的关系,对满足x(G)>(S^2+S)/2的X(G)+S阶色临界图G,证明了x(G)=△(G)+1-S,或等价地,△(G)+1-[((8△(G)+17^(1/2)-3/2]≤X(G)≤△(G)+1,这一结果部分改进了Brooks经典不等式X(G)≤△(G)+1,并完全刻画n+3(n≥4)个顶点的n-临界图的结构。

In this paper, the relation between the chromatic number X（G） and maximum degree A（G） of some given graphs G is researched. Let G be a （x（G）＋s）-order eolour-critical graph with X（G） 〉 s2＋s/2, this paper proves that A（G） = X（G） ＋ s - 1 or equivalently A（G） ＋ 1 - [8（G）＋17-3/2] ≤ X（G） ≤ △（G） ＋ 1, which partly improves a classical result due to Brooks as follow： x（G） ≤A（G） ＋ 1. And completely characterizes the structure of n-critical graph with order of n ＋ 3（n≥ 4）.