首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 156 毫秒
1.
讨论了最大度为5的平面图G的2-距离列表染色问题.给出了图G的2-距离列表色数χl2(G)的一些性质:1)若g(G)≥6,则χl2(G)≤11;2)若g(G)≥7,则χl2(G)≤9;3)若g(G)≥8,则χl2(G)≤8.其中,g(G)为图G的围长.  相似文献   

2.
设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g相似文献   

3.
图G的平方G2定义为顶点集V(G)=V(G2), 并且uv∈E(G2)当且仅当u和v之间的距离至多为2. G2的色数χ(G2)是指使得G2存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G2)≤3Δ(G)+1;  如果mad(G)≤4且Δ(G)≥8, 则χ(G2)≤3Δ(G)+5.  相似文献   

4.
令λp,q(G)为图G的L(p,q)-标号数,其中p和q是正整数且p≥q.证明了若G是围长g(G)≥6的平面图,则λp,q(G)≤(2q- 1)△(G) +4p +6q-5;若G是围长g(G)≥6且△(G)≠5的平面图,则λp,q(G)≤(2q-1)△(G)+ 10p-2q-4.这一结果暗含着对于g(G)≥6且△(G)≠5的平面图G,Wegner的猜想成立.  相似文献   

5.
本文提出以下猜想:若θ(G)=2,则χ(G)≤9;若θ(G)≥3,则χ(G)≤6θ(G)-1。证明了当 |S|∈{p,p-1,p-2,p-3,p-4,p-5}时,该猜想是正确的。  相似文献   

6.
图G的无圈边着色是指图G的一个正常边着色且不含双色的圈.图G的无圈边色数是指图G的无圈边着色中所用色数的最小者,用x’a(G)表示;证明了如果G是一个D中的顶点不与3-面相关联,3-顶点不与D中的顶点相邻且Δ(G)≥6的平面图,则x’a(G)≤Δ(G)+1。  相似文献   

7.
令V(G)、E(G)、Δ(G)和χ(G)分别为G的顶点集、边集、最大度和色数。图G的平方图,记为G2,指的是一个图满足条件:V(G2)=V(G),并且uv∈E(G2)当且仅当1≤dG(u,v)≤2。证明了若G是Δ(G)≤6且围长g(G)≥5的平面图,则χ(G2)≤Δ(G)+8。  相似文献   

8.
给定一个图G=(V(G),E(G)),图G的(s,t)-松弛强边着色数是指使得图G有(s,t)-松弛强k边着色的最小k值,记作χ′(s,t)(G).证明了在图G中,如果mad(G)<3,Δ≤7,那么χ′(0,1)(G)≤3Δ-1;同时证明了对于任意一个平面图G,如果g(G)≥7,Δ≥4,那么χ′(0,1)(G)≤[5△/2]  相似文献   

9.
设G是一个顶点集为V(G),最小度为δ(G),独立数为α(G)的图,k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V(F)都有dh G(x)=k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ(G)≥k+2,且α(G)≤4k(δ-k-1)/(k+1)2,则图G是一个分数k一致图。  相似文献   

10.
设 f 表示图 G 顶点上的标号函数,定义 b(G)=min max{f(u)+f(v)|边(u,v)∈E(G)}.其中图 G 是简单、连通图。称 b(G)为 G 的和宽.期望利用 b(G)来研究带宽 B(G)。证得2B(G)≤b(G)-1及 b(G)≥p(G)+δ(G),b(G)≥△(G)+2,b(G)+b(G~C)≥2p(G)+2,p(G)=|V(G)|。  相似文献   

11.
研究了n个顶点的连通二部图当控制数γ(G)≥3,最大度Δ(G)≥n-γ(G)-1时的最大边数。  相似文献   

12.
证明了如果图G是一个连通的平面图且不包含C8和相邻三角形,那么肯定存在一棵G的生成树T使得χb(G,T)≤4。  相似文献   

13.
设G为n阶连通图,集合S称为图G的全控制集,如果V(G)的每个顶点都和S中某点相邻。图G的全控制数,记为γt(G),是图G的全控制集的最小基数。证明了对阶数n≥3且T≠K1,n-1的树T,γt(T)=min{(2n/3),n-l,[n/2]+l-1},这里l表示树T中叶子的数目。  相似文献   

14.
点关联较少3-面的平面图的全染色   总被引:1,自引:0,他引:1  
证明了对每点至多关联2个3-面的平面图,全染色猜想成立. 对每点至多关联2个3-面且Δ(G)≥8的平面图,有xT(G)=Δ(G)+1.对每点至多关联[Δ(G)/2」个3-面且Δ(G)≥9的平面图,有xT(G)=Δ(G)+1.  相似文献   

15.
图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i~l(G)≤Δ+3.  相似文献   

16.
提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.  相似文献   

17.
设G是不含相交5-圈的平面图,证明了如果G是连通的并且δ(G)≥2,则G包含一条边xy,使得d(x)+d(y)≤10或者一个2-交错圈。由这个结果可以得到G的线性2-荫度la2(G)≤「Δ/2+5,改进了不含5-圈的平面图的线性2-荫度的已知上界。  相似文献   

18.
极大平面图 G的面色数不超过 4,且其为 4当且仅当G为 4阶完全图  相似文献   

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

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