共查询到19条相似文献,搜索用时 78 毫秒
1.
2.
王维凡 《辽宁大学学报(自然科学版)》1995,22(A00):21-25
平面图G(V,E,F)的完备色数χc(G)是使得集合V(G)∪E(G)∪F(G)中的相邻点,相邻边、相邻面、相关联的点边、相关联的点面及相关联的边面均染为不同颜色的最少颜色数。一个无割点的外平面称为开外平面图。如果它的每一个内面的边界至少含一条外边。本文证明了:若G为开外平面图且其顶点最大度△(G)≥6,则χc(C)=△(G)+1。 相似文献
3.
王维凡 《辽宁大学学报(自然科学版)》1994,(4)
本文证明了:若G为简单外平面图,则(i)当Δ(G)≥4时,Δ(G)≤Xe(G)≤Δ(G)+1;(ii)当Δ(G)=3时,4≤Xe(G)≤5,且Xe(G)=5当且仅当G-E'含有奇圈分支,其中E'为G的割边集合,Δ(G)为G的点最大度,Xe(G)为G的边面全色数。 相似文献
4.
研究了最大度顶点互不相邻的高度图的全色数.得到:设图G的最大度顶点是互不相邻的,且δ(G)≥34|V(G)|,则xT(G)=Δ(G)+1 相似文献
5.
一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立. 相似文献
6.
一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a'(G)是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a'(G)≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a'(G)=4的充分条件,拓展了该领域的相关结果. 相似文献
7.
孔立 《烟台师范学院学报(自然科学版)》2005,21(2):106-108
双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上.证明了对于最大度至少是6的双外平面图,有Xef(G)≤△(G) 1,其中△(G)是G的最大度. 相似文献
8.
设G是无割点平面图,xefl(G)为G的边面List选择数。本文证明了若G为最大度Δ(G)≥6的无割点外平面图,则xefl(G)=Δ(G)。 相似文献
9.
图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行着色, 使得相邻或者相关联的两个元素染不同的颜色, 图G的全色数是使G存在k-全染色的最小整数k. 对最大度为Δ的平面图, 如果(1),Δ(G)≥5且任何点至多关联一个长度至多为5的圈, 或者(2),Δ≥4, 不含3-圈并且任何点至多关联一个长度至多为6的圈, 则它的全色数为Δ(G)+1。 相似文献
10.
最大度是6不含相邻k-圈的可平面图的边染色 总被引:1,自引:1,他引:0
倪伟平 《华东师范大学学报(自然科学版)》2010,2010(5):20-26
运用Discharge方法和临界图性质证明了,最大度是6且任意两个长度至多是6的k-圈不相邻的可平面图是第一类图. 相似文献
11.
连广昌 《南京邮电大学学报(自然科学版)》1995,(2)
证明了图的逻辑积的色数公式x(G1∧G2∧…∧Gn)≤min{x(G1),x(G2),…,x(Gn)},边色数有并作如下猜想:x(G1∧G2∧…∧Gn)=min{x(G1),x(G2),…,x(Gn)}. 相似文献
12.
13.
Vizing(1964年)和Gupta(1966年)各自独立地证明了边着色中的重要定理:对任何简单图G,表X′(G)=△或X′(G)△+1。但确定一个图G的边色数仍是一个尚未解决的问题。本文利用系列平行图的结构性质,确定了它的边色数。 相似文献
14.
田双亮 《西北民族学院学报》2005,26(2):1-3
通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图. 相似文献
15.
16.
林年锋 《南京师大学报(自然科学版)》2004,27(4):28-31
图G的平方图,记作G^2,是一个以原图的顶点集为顶点集,若原图中两点的距离不大于2则连以边所成的图.本文确定了圈的平方图的色数.对于外部平面图,得到以下结论:设G是一个最大度为△(G)的简单连通外部平面图,G≠C5.则x(G^2)≤△(G) 2. 相似文献
17.
证明了,任意正整数k≥2,存在点可区别边色数为2k+1的k+1-正则图;任意正整数m≥4,存在点可区别边色数为m的偶图. 相似文献
18.
19.