n阶q-树的三次整子图色性的注记(上)  

A NOTE OF CHROMATICITY OF THE THREE-DEGREE INTEGRAL SUBGRAPH OF q-TREE

作　　者：刘颖[1] 刘焕平[1] 

机构地区：[1]哈尔滨师范大学

出　　处：《哈尔滨师范大学自然科学学报》2004年第6期13-16,共4页Natural Science Journal of Harbin Normal University

摘　　要：Chao等[1 ] ,韩伯棠[2 ] 和ThomasWanner[3] 分别仅用色多项式表征了 q-树和 q -树的 (一次 )整子图 ;刘象武等又在参考文献 [4]中表征了当最小度δ(G)≠q - 3时 ,q -树的二次整子图的色性 .本文证明了n阶 q -树的三次整子图G的色多项式为 :P(G ;λ) =λ(λ - 1 )… (λ - q + 1 ) 4 (λ - q) n- q- 3且G为 q + 1色图 ,色分划数为8;反之 ,在G的一个 q + 1着色下 ,若恰有一个二色子图不连通 ,则G是n阶 q -树的三次整子图 .Chao etc. [1] ,Han Botang [2] and Thomas Wanner [3] characterized q-tree and the integral subgraph of q-tree only by their chromatic polynomials respectively.Then XiangWu-Liu etc.characterized the two-degree integral subgraph of q-tree when the least degree of the subgraph satisfied δ(G)≠q-3 in [4]. In this paper ,we show the chromatic polynomial of three-degree integral subgraph G of q-tree on n vertices is P(G;λ)=λ(λ-1)…(λ-q+1) 4(λ-q) n-q-3 .. And G is a (q+1)-colorable graph , its number of color partitions is eight. On the contrary , under a (q+1) colored , if it has just one disconnected two color subgraph,then G which has the chromatic polynomial like above is a three-degree integral subgraph of q-tree on n vertices.

关 键 词：子图 色性 色多项式 注记 分划 最小度 表征 参考文献 证明 

分 类 号：O157.5[理学—数学]