共查询到18条相似文献,搜索用时 109 毫秒
2.
琼吉 《青海师范大学学报(自然科学版)》2011,27(1):5-8
本文围绕列表着色展开讨论,将列表着色方面的已有结论进行了整理和简要的证明及补充说明.本文对一些猜想的特殊情况进行了论证. 相似文献
3.
4.
5.
曲面嵌入图的着色的研究起源于Heawood地图着色定理.本文在对原始文献进行研究的基础上,论述Thomassen在三色定理与列表着色、曲面嵌入图的着色、色多项式和着色的数目等方面的工作.他的研究受到了Mohar,Thomas和Hutchinson等许多数学家的关注. 相似文献
6.
文章首先根据模的知识定义了简单图的边着色矩阵,给出了边着色矩阵对于二部图着色问题的表示,并具体给出了二部图的边着色矩阵的构造方法. 相似文献
7.
如果对于图G的每个满足|L(v)|=k(其中v为G的任意顶点)的列表分配L,G都存在一个L-着色,使得G的每个顶点至多有d个邻居与其自己着有相同的颜色,则称图G是(k,d)*-可选的。在只用欧拉公式和图的结构性质研究2-连通平面图的(3,1)*-列表着色的基础上,研究欧拉公式在平面图的(3,1)*-列表着色中的应用,证明欧拉公式在研究有割点的平面图的(3,1)*-列表着色时也是有效的。 相似文献
8.
姚潇彦 《浙江师范大学学报(自然科学版)》2011,34(3)
令G是一个最大度为△(G)的平面图.运用Dischanging方法,进一步探究△(G)≥6的平面图的边列表色数,得到了最大度为6且不含4-圈和7-圈的平面图的边列表色数为△,全列表色数为△+1. 相似文献
9.
尹杰杰 《海南大学学报(自然科学版)》2013,(4):295-299,302
利用Groebner基方法给出了任意有限图的尼一顶点着色与k-边着色的求解方案,从而求得图的后.顶点着色方案和顶点色数,k-边着色方案和边色数. 相似文献
10.
文章给出了边列表染色和顶点列表染色的定义,证明了对轮图,边选择数x (G)=△(G),点选择数xLV(G)=4,点边选择数xLVE(G)=△(G)+1. 相似文献
11.
马刚 《安徽大学学报(自然科学版)》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)=Δ. 相似文献
12.
简单连通图G的邻点可区分全染色(邻强边染色)是图G的一个正常全(边)染色,并且使得任意两个相邻的点u,v满足C(u)≠C(v),其中C(u)={f(u)}∪{f(uw)|uw∈E(G),w∈V(G)}(C(u)={f(uw)|uw∈E(G),w∈V(G)}).满足图G有一个邻点可区分全染色(邻强边染色)所用的最少颜色数记为χat(G)(χ′as(G)).图G的最大度记为Δ(G).本文给出了χat(G)=Δ(G)+3的一个充分条件和χ′as(G)=Δ(G)+2的一个充分条件. 相似文献
13.
设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E(G)到{1,2,…,k}的映射,且满足u,v∈V(G),u≠v,有S(u)≠S(v),其中S(u)={f(uw)|uw∈E(G)}.数min{k|G存在k-VDPEC染色}称为图G的点可区别正常边色数,记为χs′(G),研究了Wm∨Pn(n≤3)的点可区别边染色,给出了Wm∨Pn(n≤3)的点可区别边色数. 相似文献
14.
一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a'(G)是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a'(G)≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a'(G)=4的充分条件,拓展了该领域的相关结果. 相似文献
15.
讨论了最大度为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的围长. 相似文献
16.
设μ1(G)表示一个图G的Mycielski图.广义Mycielski图μm(G)是Mycielski图μ1(G)的自然推广.研究广义Mycielski图μm(G)的边染色问题,运用换色技巧证明了:若G是不同于K2的连通简单图,则对任何m≥2,μm(G)是第一类的,即边色数等于最大度.推广了现有关于Mycielski图的边色数的相关结果. 相似文献
17.
图\,$G$\,的点可区别星边边色数, 记为\,$\chi'_{\rm vds}{(G)}$, 是图\,$G$\,的点可区别星边染色所用色的最小数目. 得到了一些特殊图的星边染色,
并证明了若图\,$G$\,是一个最小度不小于\,5, 且顶点数不超过\,$\Delta^7$\,的图时, $\chi'_{\rm vds}{(G)}\leqslant {14\Delta^{2}}$, 其中\,$\Delta$\,是图\,$G$\,的最大度. 相似文献
18.
图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△(G)+2,其中△(G)为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△(G)+3. 相似文献