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

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

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

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

出　　处：《哈尔滨师范大学自然科学学报》2005年第1期4-6,共3页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 et al. ~[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 Liu Xiangwu et al. 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.

关 键 词：Q-树 三次 n阶 色性 注记 色多项式 二次整子图 最小度 表征 图G 分划 连通 

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