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

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-树的三次整子图.

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

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 -树的三次整子图 .

关于q-树二次整子图和n阶加点q-树色多项式的注记

在这篇文章中我们成功地仅用色多项式表征了最小度不等于q-3的q-树的二次整子图和n阶加点q-树,即当图的最小度δ(G)≠q-3时,n阶图G具有色多项式P(G;λ)=λ(λ-1)…(λ-q+2)(λ-q+1)~3(λ-q)^(n-q-2),n≥q+2,当且仅当G是n阶q-树的二次整子图或n阶加点q-树.