关于图的3—色数

ON THE 3-CHROMATIC NUMBER OF GRAPHS

对 Harary 在文献[1]中的 n一色数的 n=3,进行了讨论,得到了 X_3(G),不可改进的上下界以及常见特殊图簇的 x_3(G),并得到了 X_3(G)与 X_3(?)、 X_3(G)与 X(?)不可改进的关系。

Let x_3(G)and x(G)denote the 3—chromatic number and the chromatic num-ber of a graph G respectively,△(G)is the maximum edge's degree of G,the following re-suits are obtained:(1)An upper and a lower bounds of x_3(G)are obtained;(2)If G istree,then x_3(G) is equal to △(G);(3)A relation between x_3(G)and X_3(?)and one be-tween X_3(G)and X(?)are obtained,respectively,where the(?)denotes complement graph ofa graph G.