共查询到16条相似文献,搜索用时 78 毫秒
1.
不含四圈,三圈不重点的平面图全染色的一个结论 总被引:1,自引:0,他引:1
孙向勇 《山东大学学报(工学版)》2007,37(3):118-121
设G是一个图,Δ(G)是G的最大度.本文对3 圈不重点的,且不含从4到k圈的平面图,得出的结论有:如果(Δ,k)分别是(6,4),(5,5),(4,11),则G的全染色数是Δ(G)+1. 相似文献
2.
关于3-圈不重点的平面图全染色的一个结论 总被引:3,自引:0,他引:3
孙向勇 《山东建筑大学学报》2006,21(4):374-376
给定一个图G,G的全k可染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一颜色。图G的全染色数xτ(G)是指使G全k染色的最小整数k。△(G)是G的最大度,显然任何一个图不会是全△可染的,但是Vizing猜测任何一个图一定是全△+2可染的。而这个全染色猜想,对平面图也仍是没有得到解决的。本文利用欧拉公式和重新分配的方法,对3-圈不重点的平面图进行了讨论,得出结论:最大度△≥8的任何两个3-圈不重点的平面图一定是全△+1可染的。 相似文献
3.
孙向勇 《山东建筑工程学院学报》2006,(4)
给定一个图G,G的全k可染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一颜色。图G的全染色数xT(G)是指使G全k染色的最小整数k。Δ(G)是G的最大度,显然任何一个图不会是全Δ可染的,但是Vizing猜测任何一个图一定是全Δ 2可染的。而这个全染色猜想,对平面图也仍是没有得到解决的。本文利用欧拉公式和重新分配的方法,对3-圈不重点的平面图进行了讨论,得出结论:最大度Δ≥8的任何两个3-圈不重点的平面图一定是全Δ 1可染的。 相似文献
4.
双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上。设G是一个双外平面图,V(G),E(G),F(G)分别为双外平面图G的点集,边集和面集。G的全色数XT(G)是使得V(G)UE(G)中的任意两个相邻或相关联的元素间均染不同颜色的最少颜色数。本文证明了对最大度为6的双外平面图,全色数是△(G)+1,其中△(G)为G的最大度数。 相似文献
6.
研究了不含5-圈,且每个4-圈,6-圈或7-圈不与长度小于8的圈有公共边的平面图的结构,证明了8个结论。为研究平面图的3着色问题,探讨平面图结构的相关性质,证明这个命题提供了前提依据。 相似文献
7.
8.
为了解决图的邻点可区别全染色问题中一个图的色数算法问题,以外平面图的结构研究为基础,采用分析法和数学归纳法,对一类外平面图的邻点可区别全染色问题进行了研究,并得到了它的邻点可区别全色数. 相似文献
9.
设G是无割点平面图,x^efl(G)为G的边面List选择数。本文证明了若G为最大度Δ(G)≥6的无割点外平面图,则x^efl(G)=Δ(G)。 相似文献
10.
若图G存在边e使G-e为外平面图,则称G为几乎外平面图.本文证明了,连通几乎外平面图G是第二类的当且仅当G是奇圈或△(G)=3且G有一个2-连通子图G′含有唯一的2-度点.同时,Fiorni关于外平面图边色数的结论得以推广. 相似文献
11.
Halin图G=T∪C,其中T为每一非悬挂点(内点)度数至少为3的平面树,C为连接T的所有悬挂点的圈.文章分别讨论了Halin图的星色数、面色数及分数色数. 相似文献
12.
13.
应用概率方法中的第一矩量原理和Markov不等式,证明了对于最大度为Δ的n阶图G,当Δ≥2时,其点可区别的边色数χv′d(G)≤nΔ(n-1),当n≥3,Δ≥1时,其点可区别的全色数χvt(G)≤2 nΔ(n-1). 相似文献
14.
针对以r为参数的直径为 2的图的 (2 ,r)路色数的计算复杂性问题 ,从直径为 2的图及任意给定的整数r ≥ 3,图的 (2 ,r) 路色数问题是NP 完全的入手 ,给出直径为 2的 (2 ,2 )的路色图的一个好的刻划 ,并由此给出该问题一个多项式时间算法 ,从而解决了以r为参数的直径为 2的图的 (2 ,r)路色数问题的计算复杂性分类 相似文献
15.
李雪峰 《西安邮电学院学报》2005,10(2):135-136
设P(G;λ)是图G的色多项式,如果对任意图H,当P(H;λ)=P(G;λ)时,都有H和G同构,则称图G是色唯一的。本文给出了由两个块H和K2构成的图G是色唯一的当且仅当H是色唯一点可迁的。 相似文献