正则图与其补图的全色数

Total Chromatic Numbers of a Regular Graph and Its Complementary Graph

利用全图的性质研究图的全色数.给出正则图及其补图的全色数之间的关系。得到:若 G 是 k-正则图(2≤k<p-2),则p+1≤X_T(G)+X_T(G^c)≤2(p-1),(p-k)(k+1)≤X_T(G)·X_T(G^c)≤4k(p-k-1)。其中 p=|V(G)|,G^c 为 G 的补图。从而加强了文〔2〕、〔6〕中给出的部分结果。

We use properties of total graphs in studying the total chromatic number X_T(G)of a graph G.What we have obtained is as follows: Let G be a k-regular graph(2≤k<p-2),then p+1≤X_T(G)+X_T(G^c)≤2(P-1), (p-k)(k+1)≤X_T(G)·X_T(G^c)≤4k(p-k-1). where p=|V(G)|, G^c is the complementary graph of the graph G.