共查询到18条相似文献,搜索用时 125 毫秒
1.
在图G的一个正常点染色c中,对于图中任意一点v,如果每种颜色在点v的邻点中至多出现k-1次,这个染色就称为图G的一个k-frugal染色。关于无4-圈和5-圈的平面图的k-frugal列表染色问题,有以下两个结论:(1)对于一切不含4-圈和5-圈的平面图,如果其最大度满足Δ≥3k+8,其k-frugal列表色数小于等于「Δ/(k-1)+2;(2)一切不含4-圈和5-圈的平面图,则其k-frugal列表色数小于等于「Δ/(k-1)+5。 相似文献
2.
如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用差值转移方法并结合平面图的结构性质,证明了不含相交三角形和4圈的平面图的无圈边色数不超过△(G)+6。 相似文献
3.
图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△(G)+2,其中△(G)为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△(G)+3. 相似文献
4.
张埂 《烟台大学学报(自然科学与工程版)》2013,26(4):243-245,249
图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3. 相似文献
5.
许振宇 《山东科技大学学报(自然科学版)》2004,23(3):95-97
设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N.Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立,且它们的色数均不超过最大度加1。 相似文献
6.
关于无5-圈,8-圈和9-圈平面图的3-选色 总被引:3,自引:0,他引:3
张海辉 《兰州大学学报(自然科学版)》2005,41(3):93-97
图G的选色数,记为xl(G),定义为最小的自然数k,使得满足对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的列表中选择时,总存在图G的一个顶点的正常着色.证明了每个围长至少为4且不含5-圈,8-圈和9-圈的平面图是3-选色的. 相似文献
7.
马刚 《安徽大学学报(自然科学版)》2017,41(4)
对图G的一个正常边染色,如果图G的任何一个圈至少染3种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G),都有φ(e)∈L(e),则称φ为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.论文证明:若图G是一个平面图,且它的最大度Δ≥5,围长g(G)≥7,则a′_(list)(G)=Δ. 相似文献
8.
不含3-圈平面图的线性染色 总被引:1,自引:0,他引:1
王侃 《浙江师范大学学报(自然科学版)》2011,34(2)
运用Discharging方法,研究了平面图的线性染色问题,证明了一个没有3-圈的平面图G的线性色数lc(G)≤[3△(G)/2]+2,其中△(G)表示G的最大度. 相似文献
9.
丁伟 《山东大学学报(理学版)》2012,47(6):76-79
如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。 相似文献
10.
用△(G)表示图G的顶点最大度.对平面图,当△(G)≥11时,已证明Vizing和Behzad的图的全色数猜想(TCC)是正确的.运用Dischrge方法证明了最大度为9且不含4-圈的平面图的全色数等于10. 相似文献
11.
设 G 是一个含有4k 个顶点的简单图,若δ(G)≥2k,则 G 包含 k -2个4-圈和1个8-圈,使得这 k -1个圈是相互独立的。在此基础上证明了:若 G 是一个含有4k(k≥4)个顶点的图,δ(G)≥2k,则下列两种情况中至少有一种成立:(1)G 包含 k -3个4-圈和1个12-圈;(2)G 包含 k -4个4-圈和2个8-圈。且不论哪一种情况成立,这k -2个圈点不交。 相似文献
12.
线性k-森林是每一个连通分支均为长度不超过k的路的图。一个图G的线性k-荫度是将图G的边集合能分解成的线性k-森林的最少数目,用lak(G)来表示。证明了:若G为不含4-圈和5-圈的平面图,则la2(G)≤「Δ(G)+1/2■+4。 相似文献
13.
张静雯 《浙江师范大学学报(自然科学版)》2011,34(3)
运用Discharging方法,证明了最大度为6且不含5-圈和相邻4-圈的简单平面图是7-全可染的.所得结果改进了现有文献的相关结果. 相似文献
14.
设Φ是图G的一个正常的顶点染色, 若Φ的任何两种不同颜色所染的顶点数目至多相差1,称是G的一个均匀染色。对于不含4,5,6-圈的平面图, 且最大度Δ≥9,那么G存在均匀Δ-染色。 相似文献
15.
《陕西师范大学学报(自然科学版)》2015,(5)
利用权转移方法证明了每个最小度至少为5并且最小边度至少为11的IC-平面图G含有一个最大度max{d(u),d(v),d(w)}≤17的3-圈。 相似文献
16.
完全三部图的5圈分解问题 总被引:1,自引:0,他引:1
给出了一些可以5圈分解的具体的完全三部图;利用一个引理构造了若干可以5圈分解的完全三部图系列;给出一个完全三部图可以5圈分解的必要条件,并猜测它也是充分条件. 相似文献
17.
对于平衡二部图G=(V1,V2;E),|V1|=|V2|=3k,其中k≥1,如果最小度δ≥2k,则 G或者包含k个点不交的六圈,或者包含k-1个点不交的六圈和一个四圈。 相似文献
18.
研究了没有7-圈的连通平面图的BB-染色问题。应用经典的Discharging方法,证明了没有7-圈且不含相邻4-圈的连通平面图G,存在G的一棵生成树T,使得( G,T)是BB-4-可染的。这一结果进一步拓展了平面图的BB-4-可染的充分条件。 相似文献