共查询到20条相似文献,搜索用时 0 毫秒
1.
设G是无割点平面图,x^efl(G)为G的边面List选择数。本文证明了若G为最大度Δ(G)≥6的无割点外平面图,则x^efl(G)=Δ(G)。 相似文献
2.
3.
若图G存在边e使G-e为外平面图,则称G为几乎外平面图.本文证明了,连通几乎外平面图G是第二类的当且仅当G是奇圈或△(G)=3且G有一个2-连通子图G′含有唯一的2-度点.同时,Fiorni关于外平面图边色数的结论得以推广. 相似文献
4.
若图G存在边e使G -e为外平面图 ,则称G为几乎外平面图 .本文证明了 ,连通几乎外平面图G是第二类的当且仅当G是奇圈或Δ(G) =3且G有一个 2 连通子图G′含有唯一的 2 度点 .同时 ,Fiorni关于外平面图边色数的结论得以推广 . 相似文献
5.
6.
孙向勇 《山东工业大学学报》2007,37(3):118-121
设G是一个图,Δ(G)是G的最大度.本文对3-圈不重点的,且不含从4到k圈的平面图,得出的结论有:如果(Δ,k)分别是(6,4),(5,5),(4,11),则G的全染色数是Δ(G)+1. 相似文献
7.
双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上。设G是一个双外平面图,V(G),E(G),F(G)分别为双外平面图G的点集,边集和面集。G的全色数XT(G)是使得V(G)UE(G)中的任意两个相邻或相关联的元素间均染不同颜色的最少颜色数。本文证明了对最大度为6的双外平面图,全色数是△(G)+1,其中△(G)为G的最大度数。 相似文献
8.
不含四圈,三圈不重点的平面图全染色的一个结论 总被引:1,自引:0,他引:1
孙向勇 《山东大学学报(工学版)》2007,37(3):118-121
设G是一个图,Δ(G)是G的最大度.本文对3 圈不重点的,且不含从4到k圈的平面图,得出的结论有:如果(Δ,k)分别是(6,4),(5,5),(4,11),则G的全染色数是Δ(G)+1. 相似文献
9.
李晓东 《哈尔滨理工大学学报》2001,6(1):100-102,106
图的全染色是染色理论的重要内容,全染色猜想:设G是一个简单图,则χT(G)≤△(G) 2是一个至今未解决的问题,证明了对于一些图类全染色猜想是正确的。 相似文献
10.
文章给出了边列表染色和顶点列表染色的定义,证明了对轮图,边选择数xE^L(G)=△(G),点选择数xV^L(G)=4,点边选择数xVE^L(G)=△(G) 1。 相似文献
11.
Δ(G)=4,5,6时的Halin图的边面全色数 总被引:2,自引:0,他引:2
刘景发 《上海第二工业大学学报》2000,17(2):20-25
本文证明了,对Δ(G)=4,5,6进的Halin图G,有xef(G)≤6,这里xef(G)表示图G的边面全色数,Δ(G)表示G的最大度数。 相似文献
12.
关于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可染的。 相似文献
13.
孙向勇 《山东建筑工程学院学报》2006,(4)
给定一个图G,G的全k可染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一颜色。图G的全染色数xT(G)是指使G全k染色的最小整数k。Δ(G)是G的最大度,显然任何一个图不会是全Δ可染的,但是Vizing猜测任何一个图一定是全Δ 2可染的。而这个全染色猜想,对平面图也仍是没有得到解决的。本文利用欧拉公式和重新分配的方法,对3-圈不重点的平面图进行了讨论,得出结论:最大度Δ≥8的任何两个3-圈不重点的平面图一定是全Δ 1可染的。 相似文献
14.
为了解决图的邻点可区别全染色问题中一个图的色数算法问题,以外平面图的结构研究为基础,采用分析法和数学归纳法,对一类外平面图的邻点可区别全染色问题进行了研究,并得到了它的邻点可区别全色数. 相似文献
15.
利用H.P.Yap在文献[2]中给出的方法,给出了关于重图边着色的两个新结果,为较精确地估计重图的边色数提供了可行的方法。 相似文献
16.
吕闯 《吉林化工学院学报》2010,27(4):91-94
图染色及色数问题是图论中的一个重要内容,也是图论中的一个十分活跃的领域,同时有着深刻而丰富的理论结果和广泛的实际应用,其理论和方法在离散数学中占有重要地位.本文在图的b-染色数和b-连续概念的基础上提出图的b-边染色数及b-边连续的概念,给出了路图、圈图以及满n叉树图的b-边染色数,并且证明了这些图都是b-边连续的. 相似文献
17.
18.
19.
极大平面图的色数研究 总被引:1,自引:0,他引:1
王绍文 《北京机械工业学院学报》1998,13(4):22-26
以极大平面图的结构研究为基础,采用常规的数学推理方法研究极大平面图的点色数问题。运用“并行(或平行)数学归纳法”证明了由“面内加点”或“边上加点”方法所构造的任意阶极大平面图是可四着色的。 相似文献
20.
刘景发 《上海第二工业大学学报》2000,17(2)
本文证明了:对△(G)=4,5,6时的Halin图G,有xef(G)≤6.这里xef(G)表示图G的边面全色数,△(G)表示图G的最大度数. 相似文献