图的一类新双变量色多项式  

A class of new two-variable chromatic polynomials

作　　者：唐晓清[1] 刘念祖[2] 王汉兴[2] 白延琴[1] 

机构地区：[1]上海大学理学院,上海200444 [2]上海立信会计学院数学与信息学院,上海201620

出　　处：《兰州大学学报（自然科学版）》2012年第2期106-112,共7页Journal of Lanzhou University(Natural Sciences)

基　　金：上海市教育委员会科学基金项目(05QZ01);上海市教育委员会创新重点项目(12ZZ193);国家自然科学基金项目(60872060)

摘　　要：根据Klaus Dohmen等提出的图的新双变量色多项式概念,探究了一般图关于此定义的减边公式,利用它反复迭代后可以方便地求得任何图的新双变量色多项式,还利用它深入探讨了一些特殊图的新双变量色多项式公式.同时还探究了运用包含等偏序关系,利用Mobius反演法和"格子剖分"法求得图的新双变量色多项式.最后探讨了共点图的新双变量色多项式公式以及图的顶点和边与色多项式的关系.A new two-variable chromatic polynomial concept of graph was proposed by Klaus Dohmen et al. A general formula was achieved by us after a hard study and is called here the Reduction Edge Formula.Any graph＇s chromatic polynomial could be obtained conveniently when we repeated iteration with it.Some special graphs were also studied and their chromatic polynomial formulae,i.e.their explicit expressions,were obtained. At the same time,the partial order of containing relation was studies and by using Mobius inversion method, the chromatic polynomial coefficients were obtained.By using partition lattice of the vertex set,the variable number of times was got.So in the end,the chromatic polynomials obtained.Finally,the inclusion-exclusion principle was used to get a very important formula,i.e.the chromatic polynomial formula of intersection vertex graph.

关 键 词：减边公式 M(o|¨)bius反演 共点图 非同构图 

分 类 号：O157.5[理学—数学]