共查询到20条相似文献,搜索用时 468 毫秒
1.
图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.文章研究了一致膨胀图分数色数与原图分数色数之间的关系,并给出广义圈、广义轮图的分数色数. 相似文献
2.
本文从分数色数的定义和已有结论出发,针对两种不同的情况分别给出广义θ-图的分数关联色数,并由此进一步给出广义θ-图的r-冠图的分数关联色数,得到如下结论:incf(θk)={k+1 ,至少有一条路径的长不为2/k2/d-1所有路径的长均为2;incf(Ir(θk))=inc(Ir(θk))=k+r+1. 相似文献
3.
本文从分数色数的定义和已有结论出发,针对两种不同的情况分别给出广义θ-图的分数关联色数,并由此进一步给出广义θ-图的r-冠图的分数关联色数,得到如下结论:*.(注:*表示公式,见正文)
相似文献
相似文献
4.
图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.本文给出了球面经纬线图以及它的r-冠图的分数色数,分数关联色数和分数全色数. 相似文献
5.
首先给出图的分数色数、图的和运算和正规积运算的定义,然后研究图的和运算和正规积运算的分数色数,以及这些运算的分数色数之间的关系,进而得到图的和运算、正规积运算的分数色数上下界,从而完善图的四大运算分数色数与其因子的分数色数之间的关系. 相似文献
6.
图的条件色数是经典色数的推广,确定图的条件色数问题是一个NPC问题。已知广义Petersen图的3-条件色数的上界是8。证明了广义Petersen图3-条件色数的下界是4,并刻画了达到此下界的广义Petersen图。 相似文献
7.
8.
引入了一种新的图着色 :图的分数关联着色。定义了图的分数关联色数。讨论了分数关联着色的性质 ,给出了图的分数关联色数的一个下界。 相似文献
9.
10.
11.
几种特殊图形的分数色数研究 总被引:1,自引:0,他引:1
图的着色问题是图论中的一个重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.本文研究了一些特殊图形的分数色数,给出了计算这些图形分数色数的公式,并且对公式进行了证明. 相似文献
12.
超图是最一般最复杂的离散结构,是图的自然推广,但是图中的一些定义和结论并不是都能轻而易举地推广到超图中.给出超图分数着色和分数团的定义,这与特殊情形下的图的分数着色和分数团的定义是相容的,并将图的分数着色和分数团的一些结论在超图中进行了推广. 相似文献
13.
14.
图的邻点可区别全染色,相对于图的正常全染色有更强的要求,因为它要求相邻顶点具有不同的颜色集合.本文刻画了两类特殊的完全多部图、广义圈和广义Mycielski图的邻点可区别全色数. 相似文献
15.
16.
轮和路的广义Mycielski图的星全染色 总被引:2,自引:0,他引:2
图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同.图的全部星k-全着色中最小的数k称为它的星全色数.讨论轮和路的广义Mycielski图的星全染色问题,得到不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色. 相似文献
17.
邢婷文 《新疆师范大学学报(自然科学版)》2014,(1):72-77,80
图的染色问题具有广泛的实际应用背景,其与计算机网络结构、银行安全密码、电信通讯站点的频率分配以及人力资源配置等问题均有重要的联系。作为图的正常染色的自然推广,学者们提出了图的强染色(即2-距离染色)乃至 m -距离(m为正整数)染色的概念。文章在此基础上,定义了有向图的 m -距离染色,并研究了无向图和有向图的 m -距离染色问题,运用图论的相关技巧及标号排序等方法获得了圈、树、路、星图、有向圈、有向树的 m -距离色数,及一般无向图和有向图其 m -距离色数的上、下界。 相似文献
18.
进一步研究了平方图的邻点全和可区别非正常全染色问题:利用平方图的结构构造了路、圈、毛毛虫、广义星以及最大度为3且不含2度点的树的平方图,通过组合分析法得到上述5类平方图的邻点全和可区别非正常全色数. 相似文献
19.
设G是简单图,G的点和边称为G的元素。如果G的点和边的染色满足相邻或关联的元素得到不同的颜色,则称为G的正常全染色。如果G的一个正常全染色满足任意两种颜色所染元素数目相差不超过1,则称为G的均匀全染色,其所用量少染色数称为G的均匀全色数。本文确定了轮和扇的Mycielski图的均匀全色数。 相似文献
20.
用构造染色法和贪心算法研究限制最大度和最小度的任意两个图、 两个同阶图, 任意两个完全图的冠积与边冠积的b-色数和m-度, 以及在此基础上推出的部分图类的广义冠积和广义边冠积的b 色数和m-度. 相似文献