關于完全三部圖色唯一性的判定

G是簡單圖,用P(G,λ)表示圖的色多項式.若對任意簡單圖H當P(H,λ)=P(G,λ)時,都有H?G,則稱G是色唯一圖.Liu R.,Zhao H. X.和Ye C.已經(jīng)證明:當n和k為整數(shù)且滿足n≥k+2≥4,完全三部圖K(n-k,n,n)是色唯一的;當n和k滿足n≥2k≥4時,完全三部圖K(n-k,n-1,n)是色唯一的.在本文中,證明了當k是奇數(shù)且n≥k2/4+15/4≥6,或k是偶數(shù)且n≥k2/4+4≥5時,完全三部圖K(n-k,n-2,n)是色唯一的;當k是奇數(shù)且n≥k2/4+19/4≥7,或k是偶數(shù)且n≥k2/4+5≥9時,K(n-k,n-3,n)是色唯一的.

作 者： 唐凱 郝榮霞 徐蘭栓 TANG Kai HAO Rong-xia XU Lan-shuan   作者單位： 唐凱,郝榮霞,TANG Kai,HAO Rong-xia(北京交通大學,理學院,北京,100044)

徐蘭栓,XU Lan-shuan(邢臺廣播電視大學,理工系,河北,邢臺,054000) 

刊 名： 北京交通大學學報（自然科學版）  ISTIC PKU 英文刊名： JOURNAL OF BEIJING JIAOTONG UNIVERSITY  年，卷(期)： 2007 31(6)  分類號： O157.5  關鍵詞： 圖   色多項式   色唯一圖  

【完全三部圖色唯一性的判定】相關文章：

完全四部圖的色性04-26

完全圖的剖分圖的線圖的譜04-27

完全圖的倍圖的鄰點可區(qū)別全染色04-26

關于扇與完全等二部圖的聯(lián)圖的全色數(shù)04-27

關于三類五點圖的多重完全多部圖設計04-29

判定超歐拉圖的一個新方法04-29

星和完全等二部圖聯(lián)圖的點可區(qū)別均勻邊染色04-29

圖Pm ∨ Wn的點可區(qū)別邊色數(shù)04-28

直徑為3的3-正則簡單平面圖的完全刻畫04-26

每條弧都在Hamilton-路上的半完全多部有向圖04-29