Dn補圖的色唯一性

火博豐,劉儒英

(青海師范大學數學系,青海西寧 810008)

Dn補圖的色唯一性

火博豐,劉儒英

(青海師范大學數學系,青海西寧 810008)

利用伴隨多項式來討論圖的著色唯一性是近二十年來出現的新方法.用Pn表示有n個頂點的路.Dn表示把K3的一個頂點與Pn?2的一個一度頂點重迭后得到的圖.該文推廣了相關文獻的結論,得到n色唯一當且僅當n/=4且n/=8.徹底解決了這類圖的色性.

色多項式；色唯一性；伴隨多項式；伴隨唯一性

1 定義和基本引理

2 伴隨多項式相關性質及重要引理

3 Dn補圖的色唯一性

[1]邦迪J A,默蒂U S.圖論及其應用[M].北京:科學出版社,1984.

[2]Liu Ruying.Ad joint polynomialsand chromatically unique graphs[J].DiscreteMathematics,1997,172:85-92.

[3]Liu Ruying,Zhao Lian chang.A new m ethod for p roving chrom atic uniqueness of graphs[J].Discrete Mathematics,1997,171:169-177.

[4]劉儒英.Pq?1的補圖的色唯一性[J].數學研究與評論,1994,3:469-472.

[5]杜清晏.圖的參數π(G)及其圖的分類[J].內蒙古大學學報,1995,26(3):258-262.

[6]火博豐.圖的三個參數A(G),R(G)及D2(G)的關系[J].青海師范大學學報,1998,2:1-6.

[7]劉儒英.圖的伴隨多項式[J].青海師范大學學報,1990,3:1-9.

[8]Du Qingyian.Chrom aticity of com p lem ents of paths and cycles[J].D iscrete Mathem atics,1996,162:109-125.

[9]火博豐,劉儒英.關于Dn補圖色性證明的一個重要引理[J].青海師專學報,2005,3:12-15.

[10]Cvetkovi D,Doob M,Sachs H.Spectra of graphs[M].New York:Academ ic Press,1980:72-79.

[11]趙海興,火博豐,劉儒英.路的補圖的色唯一性[J].數學研究,2000,4:345-353.

[12]Du Qingyian.Onσ-equivalence andχ-equivalence of graphs[J].Journal of G raph Theory.1996,21(2):211-217.

[13]王守中,劉儒英.圈和Dn圖的補圖的色唯一性[J].數學研究與評論,1998,2:296.

[14]王力工,劉儒英.一類樹并補圖的色唯一性[J].純粹數學與應用數學,2001,17(2):126.

Chrom aticity of the complements of Dn

HUO Bo-feng,LIU Ru-ying

(Department of Mathematics,Qinghai Normal University,Xining 810008,China)

The paper show the chrom aticity of some dense graphs by em p loying the ad joint polynomial.Let Pndenote the Path of order n,Dnthe graph that identify a vertex of K3with an end-vertex of Pn?2.we generalize the conclusion and obtain that the com p lements of Dnare chromatic uniqueness if and only if n/=4 and n/=8,which com p letely solve this p roblem.

chrom atical polynomial,chrom aticity,ad joint polynomial,ad joint uniqueness

O157.5

A

1008-5513(2009)02-0268-08

2007-11-05.

國家自然科學基金(10761008),教育部自然科學重點研究項目(205170).

火博豐(1967-),副教授,研究方向：圖論.

2000M SC:05C15