ΦS-型图簇的伴随分解及其色性分析

索南仁欠,李生刚

(1.陕西师范大学数学与信息科学学院,陕西西安 710062;2.青海师范大学数学系,青海西宁 810008)

ΦS-型图簇的伴随分解及其色性分析

索南仁欠1,2,李生刚1

(1.陕西师范大学数学与信息科学学院,陕西西安 710062;2.青海师范大学数学系,青海西宁 810008)

运用图的伴随多项式的性质,讨论了图簇ΦS((kn+1)σ,nσ)∪2kSσ的伴随多项式的因式分解定理,进而证明了它们的补图的色等价性.

色多项式;伴随多项式;因式分解;色等价性

1 预备知识及准备工作

图1

图2

图3 ΨS(kσ,nσ)

图4 ΦS((kn+1)σ,nσ)

2 因式分解定理

3 色等价性分析

参考文献

[1]Body J A,Murty U S R.Graph Theory with Applications[M].Amsterdam:North-Holland,1976.

[2]周登杰.路和圈多重联图的邻点可区别E-全染色[J].纯粹数学与应用数学,2010,26(6):909-914.

[3]王艳芳.4度Cayley图的Hamilton圈分解的新方法与理论证明[J].纯粹数学与应用数学,2010,26(3):380-386.

[4]郑国彪.D-完全一致混合超图不可着色的一个充要条件[J].纯粹数学与应用数学,2011,27(3):308-312.

[5]刘儒英.求图的色多项式的一种新方法及其应用[J].科学通报,1987,32:1508-1509.

[6]Liu R Y.Adjoint polynomials and chromatically unique graphs[J].Discrete Mathematics,1997,172:85-92.

[7]张秉儒.几类图簇的伴随多项式的因式分解及其色性分析[J].数学学报,2002,45(3):529-534.

[8]马海成.构造色等价图的几种新方法[J].高校应用数学学报,2004,19(2):135-140.

[9]Read R C.An introduction to chromatic polynomials[J].Combin.Theory,1968,4:52-71.

[10]Farrell E J.An introduction to matching polynomials[J].Combin.Theory(B),1979,27:75-86.

[11]Biggs N.Algebraic Graph Theory[M].Cambridge:Cambridge University Press,1974.

[12]刘儒英.两类图的色多项式的求法[J].科学通报,1987,32:1147-1148.

[13]张秉儒.图的伴随多项式的因式分解定理及其应用[J].数学学报,2005,48(1):125-132.

[14]刘儒英.图的补图的色唯一性[J].数学研究与评论,1994,14:469-472.

[15]Zhang B R.The factorization of adjoint polynomials of class graphs and chromatically equivalence analysis[J].数学季刊,2008,23(3):376-383.

[16]侯海存,张秉儒.一类新的图簇的伴随分解定理及其补图的色等价性[J].西南师范大学学报,2010,35(4):69-73.

The factorization of adjoin polynomials of graphs of ΦS-shape and chromatic non-uniqueness analysis

Suonan Renqian1,2,Li Shenggang1

(1.College of Mathematics and Information science,Shanxi normal university,Xi′an710062,China;
2.Department of Mathematics,Qinghai Normal University,Xining810008,China)

By applying the properties of adjoint polynomials,We prove that factorization theorem of adjoint polynomials of a kind of graphs ΦS((kn+1)σ,nσ)∪2kSσ,Furthermore,we obtain chromatically equivalence of its complements.

chromatic polynomial,adjoint polynomials,factorization,chromatically equivalent graph, structure characteristics

O157.5

A

1008-5513(2013)06-0551-08

10.3969/j.issn.1008-5513.2013.06.001

2013-10-08.

国家自然科学基金(11061026,11071151).

索南仁欠(1969-),博士生,教授,研究方向：计算数学,代数组合论.

2010 MSC:05C78