火博丰,刘儒英

(青海师范大学数学系,青海西宁 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