首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 0 毫秒
1.
1988年,张忠输等证明了对于△(G)≥3的外平面图G,全色数XT(G)=△(G)+1.本文给出此结论一个简单证明,方法是全新的.  相似文献   

2.
低度平面图的边面全色数   总被引:2,自引:0,他引:2  
平面图G(V,E,F)的边面全色数X,(G)是使得集合E(G)∪ F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文提出猜想:对任何平面图G,有△(G)≤X,(G)≤△(G)+3;并对顶点度不超过3或面度均为3的平面图证明了这个猜想为真。  相似文献   

3.
极大外平面图的边面全色数   总被引:1,自引:0,他引:1  
本文给出了△(G)≤6的极大外平面图的边面全色数,其中△(G)表示G的最大度。  相似文献   

4.
设G为Δ(G)≥5的外平面图且xef(G)为G的边面全色数。本文证明了:Δ(G)≤xef(G)≤Δ(G)+1,且xef(G)=Δ(G),当且仅当G含有一个由内边组成且覆盖G的每一个最大度点的匹配。  相似文献   

5.
李琼  卜月华 《数学研究》2006,39(4):401-409
对于图G(V,E)的正常k-全染色φ称为G(V,E)的k-均匀全染色,当且仅当任意两个色类中的元素总数至多相差1.xvee(G)=m in{k存在图G的一个k-均匀全染色}称为G的均匀全色数.本文得到了两类M ycielsk i图及圈,轮图和扇形的均匀全色数.  相似文献   

6.
△-匹配与边面全色数   总被引:1,自引:0,他引:1  
设G为 (G)≥5的外平面图且  (G)为G的边面全色数。本文证明了:且当且仅当G含有一个由内边组成且覆盖G的每一个最大度点的匹配。  相似文献   

7.
一个图G的全色数χT(G)是使得V(G)∪E(G)中相邻或相关联元素均染不同颜色的最少颜色数.文中证明了,若图G只有唯一的一个4度最大度点,则χT(G)=Δ(G)+1.  相似文献   

8.
王维凡 《数学季刊》1999,14(4):76-83,
一个平面图G被称为1-树如果存在一个顶点u使得G-u是一个林。本文确定了所有1-树的边面全色数的精确上、下界,并且求出了2-连通且最大度至少为6平面图的边面全色数。  相似文献   

9.
一个平面图G被称为1-外平面图如果存在一个顶点u 使得G- u 是一个外平面图.本文证明了Melnikov 的边面染色猜想对所有1-外平面图成立.  相似文献   

10.
11.
图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.  相似文献   

12.
设d1, d2,..., dk是k个非负整数. 若图G=(V,E)的顶点集V能被剖分成k个子集V1, V2,...,Vk, 使得对任意的i=1, 2,..., k, Vi的点导出子图G[Vi] 的最大度至多为di, 则称图G是(d1, d2,...,dk)-可染的. 本文证明既不含4-圈又不含6-圈的平面图是(3, 0, 0)-和(1, 1, 0)-可染的.  相似文献   

13.
3-正则Halin-图全色数的注(英文)   总被引:4,自引:0,他引:4  
本文讨论了△(G)=3的Halin-图的金色数Xr(G)=4的充分条件,并提出了3-正则Halin-图Xr(G)=5的充分必要条件的猜想,其中△(G),Xr(G)分别表示G的最大度和全色数.  相似文献   

14.
乘积图的全色数   总被引:4,自引:0,他引:4  
杨义先  张忠辅 《应用数学》1999,12(2):108-111
本文得到了有关乘积图的全色数的一些结果,并利用这些结果证明了Mesh图和Tours-图均满足全色数猜想.特别,几乎所有的Mesh-图都是第一类图.  相似文献   

15.
关于图的均匀全色数分类   总被引:1,自引:0,他引:1  
对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.将图按均匀全色数分类,证明了简单图在若干情况下的均匀全色数定理,得到了一些联图的均匀全色数.  相似文献   

16.
设G是一个n-阶连通图(n≥2).假设火在G的某点v处燃起,消防员选择一个未着火的顶点进行保护,然后火蔓延到v的未被保护且没有着火的邻点.当火在点v处燃起时,消防员最多能保护到的顶点数记为sn(v).定义■为G的存活率.容易看到0 <ρ(G)<1.本文证明了:若平面图G不含长度从4到11的圈,则ρ(G)>1/481.  相似文献   

17.
卜月华  贾琪  朱洪国 《数学进展》2023,(6):991-1004
图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’α(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’α(G)≤Δ(G)+1.  相似文献   

18.
任玉杰 《大学数学》2004,20(2):87-88
提出了一种证明"四色猜想"的新思路.证明了"四色猜想"的一部分,即不含K3的平面图最多是-4可着色的,指出了另一部分的证明思路.  相似文献   

19.
马少仙  马刚  张忠辅 《数学研究》2006,39(3):330-334
对两个不交的图G,H,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv u∈V(G),v∈(H)},G∨H称为G和H的联图.本文得到了路Pn与完全二部图Km,n的联图Pn∨Km,n的全色数.  相似文献   

20.
若干平面图的完备色数   总被引:1,自引:0,他引:1       下载免费PDF全文
设G是无割点平面图,Xc(G)为G的点边面完备色数,p=|V(G)|.本文证明了如G为Δ(G)≥7的外平面图,或G为p≥9且Δ(G)≥p-2,或G为Δ(G)≥14的极大平面图,则 Xc(G)=Δ(G)+1.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号