共查询到20条相似文献,搜索用时 62 毫秒
1.
《汕头大学学报(自然科学版)》2016,(2)
对n圈k色的不同限制条件下的色多项式进行研究,包括:(1)给出n圈k色正常染色且满足第xi(i=1,2,…,k)种颜色恰好使用t次或不超过m次的正常染色多项式;(2)给出满足每2个相邻的染了xi色的点的间距不小于s的n圈k色正常染色的色多项式;(3)在集合和映射的层面对n圈k色的限制条件下的色多项式进行研究,从而抽象概括其数学模型并进行推广. 相似文献
2.
杜清晏 《内蒙古大学学报(自然科学版)》2000,31(6):551-561
色轨道多项式是色多项式与Polya计数公式的推广,本定义了色轨道多项式及其相应的概念加P-图,SC-图等,给出了色轨道多项式的表达式和计算方法,讨论了色轨道多项式的基本性质,作为它的一个应用,给出了项链问题的具体计数公式。 相似文献
3.
定义1设图G为含有 p个顶点的标定图 ,对其进行x———正常染色的方法数是x的一个函数 ,可表示成x的一个多项式 ,称为图G的色多项式 ,记为f(G ,x)。引理1给定图G ,设u、v∈V(G) ,e=(u ,v)∈E(G)则f(G ,x)=f(G -e ,x) -f(Goe ,x)引理2设G是含q条边k个分图的 p阶图 ,则①f(G ,x)是p次多项式 ;②f(G ,x)中xp的系数为1;③f(G ,x)xp -1的系数为 - q;④f(G ,x)中常数项为0;⑤f(G,x)=∏f(Gi,x) ,式中Gi 是G的第i个分图 ;⑥f(G,x)中 ,系… 相似文献
4.
5.
6.
7.
为了更深入地探索图的色多项式与图的结构之间的关系,以及提高求色多项式的算法速度,给出了一种有效的求色多项式的缩点递推算法。 相似文献
8.
王洪英 《山东师范大学学报(自然科学版)》2000,15(3):311-311
对有n个顶点的4-色图所含奇圈的长度的取值范围进行了研究。证明了任何一个n阶4-色图都含长度不超过8n的奇圈。 相似文献
9.
10.
当n是奇数时,Wn^*表示n阶轮相间地去掉(n—1)/2条幅所得到的图,利用图的色多项式等价性的关系,证明了W9^*是色唯一的. 相似文献
11.
王志雄 《华侨大学学报(自然科学版)》1993,14(4):412-418
给出若干类型多项式为简单图的色多项式的充分必要条件、连通图和连通双分图的色多项式必须满足的条件,研究图及其补图的色多项式对图特征的描述程度,并提出若干值得进一步探讨的问题。 相似文献
12.
程志谦 《河南科技大学学报(自然科学版)》2001,22(3):92-94
利用Whitnoy的著名结果 :P(G ,λ) = n - 1i =1 (- 1) ibiλn -i给出并证明了 :①G为连通偶图 ,当bn -1为奇数 ;②G为树 ,当bn -1=1;③分支数为k的图是偶图 ,当bn -k是奇数且bi=0 (n -k +1≤i≤n - 1)等八个定理 相似文献
13.
一个图G的亏格多项式表征了图G亏格的亏格分布情况.本文在解决M系列图的亏格多项式的基础上,利用切分与还原的方法,建立了计算类树图的亏格多项式的公式. 相似文献
14.
一类图的伴随多项式的因式分解及色性 总被引:4,自引:0,他引:4
沈素军 《青海师范大学学报(自然科学版)》2006,642(1):7-10
我们通过研究一类Г-型图的伴随多项式的因式分解,证明了这类图的补图的色等价图的结构性质和非色唯一性。 相似文献
15.
16.
当Pn和Cn分别表示具有n个顶点的路和圈,h(Pn,x)和h(Cn,x)依次表示它们的伴随多项式。本文证明了当m≥4时,h(P,x)和h(Cn,x)整除的充要条件。 相似文献
17.
利用全图的性质研究图的全色数.给出正则图及其补图的全色数之间的关系。得到:若 G 是 k-正则图(2≤k相似文献
18.
19.
陈海燕 《集美大学学报(自然科学版)》2001,6(4):384-387
G是简单图,LG表示G的线图,对LG的星色数进行了讨论,并得出了X^*(LG)=X(LG)的两个充分条件,以及一类特殊图线图的星色数的值。 相似文献
20.
本文证明了两类图P并C并D并(lC3)和P并C并D并(lC3)并(Pq-1)的补图在一定条件下是唯一的。 相似文献