关于n圈k色的限制条件下的色多项式
2016-09-03朱桂静何超林华南师范大学数学科学学院广东广州510631
汕头大学学报(自然科学版) 2016年2期
朱桂静,何超林(华南师范大学数学科学学院,广东 广州 510631)
关于n圈k色的限制条件下的色多项式
朱桂静,何超林
(华南师范大学数学科学学院,广东广州510631)
对n圈k色的不同限制条件下的色多项式进行研究,包括:(1)给出n圈k色正常染色且满足第xi(i=1,2,…,k)种颜色恰好使用t次或不超过m次的正常染色多项式;(2)给出满足每2个相邻的染了xi色的点的间距不小于s的n圈k色正常染色的色多项式;(3)在集合和映射的层面对n圈k色的限制条件下的色多项式进行研究,从而抽象概括其数学模型并进行推广.
色多项式;n圈k色;组合计数
0 引言
n圈k色正常染色问题是图论与组合数学中一个有趣的问题,文献[1-3]对圈(环)排列进行元素的重排、限距、定元计算等方面的排列计数问题进行了研究,文献[4]给出了图的色多项式的定义以及相关的图的着色定理.本文在对圈图的研究之下,着重对不同的限制条件下的n圈k色正常染色的色多项式进行了研究,同时在此基础将之上升到集合和映射的层面并进行推广计算,对研究n圈k色正常染色的意义下所构成的群的组合计数有一定的意义.
1 相关定义、引理
定义1[4]图G的不同的至多t色的着色的数目,称为图G的色多项式,记作f(G,t). n圈k色正常染色的色多项式在本文记作fn,k.
定义2[4]用n种颜色对图G的顶点进行着色,且没有相异的邻接点着相同的颜色,则称为G的一个n-顶点着色.用k种颜色对n个顶点的圈进行着色,且没有相异的邻接点着相同的颜色称为n圈k色……
登录APP查看全文
