共查询到16条相似文献,搜索用时 39 毫秒
1.
许振宇 《山东科技大学学报(自然科学版)》2004,23(3):95-97
设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N.Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立,且它们的色数均不超过最大度加1。 相似文献
2.
郑丽娜 《浙江师范大学学报(自然科学版)》2012,(1):32-36
无圈边染色是指图G的一个正常边染色,使其不产生双色圈.研究了不含特殊短圈平面图的无圈边染色问题,证明了:如果平面图G不含4到8-圈,那么G的无圈边染色数不大于Δ(G)+1. 相似文献
3.
一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立. 相似文献
4.
张埂 《烟台大学学报(自然科学与工程版)》2013,26(4):243-245,249
图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3. 相似文献
5.
图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△(G)+2,其中△(G)为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△(G)+3. 相似文献
6.
设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N.Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立,且当Δ≤4时,其色数不超过5;当Δ≥5时,其色数等于最大度。 相似文献
7.
主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。 相似文献
8.
张埂 《黑龙江科技学院学报》2010,20(4):315-317,322
为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。 相似文献
9.
研究了2-外平面图的无圈边染色问题.运用删点变换,得到了2-外平面图的结构性质;继而,运用数学归纳法,得到了图的一个无圈(Δ(G)+3)-边染色,即得到:若G是一个2-外平面图,则a’(G)≤Δ(G)+3. 相似文献
10.
11.
为研究图的无圈边色数与图的最大平均度之间的关系,利用差值转移方法和最小反例图的一些结构性质,证明了最大平均度不小于7/2的简单图G,如果其最大度不小于6,则其无圈边色数不超过Δ(G)+2. 相似文献
12.
伪Halin-图的无循环边着色 总被引:1,自引:0,他引:1
图G的无循环边着色是指图G的正常的边着色且任意的圈上不着双色.图G的无循环边色数是指对G进行无循环边着色所需的最少色数k,记为a′(G).给出了伪Halin图的无循环边色数满足猜想a′(G)Δ(G)+2,并且对任意的伪Halin图G且G≠K4,有a′(G)=Δ(G). 相似文献
13.
14.
15.
图G的无循环着色是指图G的顶点着色使得G的任何相邻的顶点不着双色且在图G没有双色圈.研究了Meredith图和系列平行图的无循环着色,证明了Δ(G)≥5的系列平行图的无循环色数a(G)≤Δ(G)+1. 相似文献
16.
图的强边染色是在正常边染色的基础上,要求每个色类的导出图是一个匹配。本文通过构造法,研究了路的幂图的强边色数至多是9,圈的幂图的强边色数至多是14。 相似文献