共查询到20条相似文献,搜索用时 15 毫秒
1.
吴建良 《山东大学学报(理学版)》1999,34(2):121-124
改进了一些边染色临界图的边数的下界.同时证明了:对没有4圈或任何两个3面都不同时关联于一个点的平面图,关于边染色的平面图猜想成立. 相似文献
2.
1968年,Vizing提出猜想:边染色临界图的独立数不大于其阶数的一半.针对不含2度点的边染色临界图,本文证明当最大度为9,10时,独立数α(G)≤(3△-3)/(5△-3)|V|和当△∈{11,…,46}时,独立数α(G)≤(15△-42)/(23△-42)|V|. 相似文献
3.
如果一个连通的第二类图G去掉任意一条边后其边色数都比图G小,则称它是一个临界图.最大顶点度为△的临界图称作△-临界图.1968年,Vizing猜想任意n阶△-临界图G边数m的下界为(nΔ-n+3)/2.Fiorini不等式和差值转移法被广泛用于研究此猜想.笔者利用Vizing邻接引理和临界图的结构性质给出了Δ-临界图在△≥6且(Δ-1)度顶点至多邻接一个四度顶点时Fiorini不等式的一个新的下界. 相似文献
4.
图G的一种均匀k-边染色是指用k种颜色去染G的边使得对G的每一个顶点v,任何两种颜色染与。相关联边的数目最多相差1.证明了对任意的大于3的整数k,Halin图都有均匀k-边染色;讨论了k=3的情况. 相似文献
5.
图G的一种均匀k 边染色是指用k种颜色去染G的边使得对G的每一个顶点v ,任何两种颜色染与v相关联边的数目最多相差 1.证明了对任意的大于 3的整数k,Halin图都有均匀k 边染色 ;讨论了k=3的情况 相似文献
6.
石少俭 《曲阜师范大学学报》1998,24(4):118-119
图的染色是图论的重要研究内容之一.平面图染色是其中的一个主要方面.有各种各样的染色方式,近来,又出现了列表染色[1].定义1称图G是k-边可选择的.如果任给e∈E(G),和边e的任给颜色集L(e),|L(e)|=t,都可以选一种颜色σ(e)∈L(e)... 相似文献
7.
研究了Halin 图的有点面约束的边染色,给出了Halin 图的有点面约束的边染色色数的一个精确结果. 相似文献
8.
9.
主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。 相似文献
10.
证明了如下结果:一个简单连通图G的全色数和列表全色数都为△+1,如果它存在一个支撑子树T使得△(G)≥6和△(G\E(T))≤2,或者△(G)≥4和△(G\E(T))≤1。 相似文献
11.
如果一个正常边染色满足相邻点的色集不同,则称为邻强边染色,其所用最少染色数称为邻强边色数.本文得到了星、扇和轮的倍图的邻强边色数. 相似文献
12.
彭锦 《华中师范大学学报(自然科学版)》1999,33(4):480-486
边愉快图是新近提出的研究课题,本文给出了边愉快图的必要条件和一类添加图或删边图成为边愉快图的充分条件;考察了几种常见图类的边愉快特征;构造了一类奇阶偶正则的边愉快图,给出了相应的边愉快标号方法;提出了值得进一步研究的一些问题。 相似文献
13.
研究正则图的均匀边染色,指出并非所有正则图都存在任意种颜色的均匀边染色.证明当l能够分解为整数k与偶数b的乘积时,l-正则图存在均匀k-边染色.同时,给出正则图均匀边染色的最小颜色数. 相似文献
14.
设G是一个简单图,f是G的一个k-正常边染色,又满足对任意的uv∈E(G),都有C(u)≠C(v),则称f为G的一个邻强边染色,简称k-ASEC,且称χas(G)=min{k|G存在k-ASEC}为G的邻强边色数,其中C(u)={f(uv)|uv∈ E(G)}.给出了路.圈、树、完全图、完全二分图、星、扇、轮的冠的邻强... 相似文献
15.
张埂 《黑龙江科技学院学报》2010,20(4):315-317,322
为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。 相似文献
16.
17.
本文在文[1]的基础上,讨论了图的边优美问题,从而得到了一些特殊图边优美的必要条件和充分条件。 相似文献
18.
讨论了无三角形的边染色图中的正常染色的路和圈,在无三角形图中改进了原有的结果。证明了在顶点的最小色度至少为d(d≥2)的条件下,边染色图G或者存在长至少为4d-2的正常染色的路,或者存在长至少为2「2d/3的正常染色的圈。 相似文献
19.
刘利群 《重庆文理学院学报(自然科学版)》2009,28(6):14-16
单图G的r-强边染色是指图的距离不超过r的任意两点可区别的边染色,所谓两点u,v间的距离是指这两个点之间的最短路的长,记为d(u,v).图G的r-强边色数x′s(G,r)表示.本文给出一类联图的2-强边色数的界,并将结论推广到r-强边色数的界. 相似文献
20.
研究立方Halin图以及一些倍图的均匀边染色,利用换色法、构造法和归纳法得出:立方Halin图和路的倍图都是均匀的,星的倍图都有均匀4-边染色. 相似文献