图的邻和可区别染色

来源 :河北工业大学 | 被引量 : 1次 | 上传用户:lan_lang_
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文所考虑的图均为有限、无向、简单图,分别用V(G)和E(G)表示图G的顶点集和边集.图G的一个k-全染色是指从V(G)∪E(G)到{1,2,…,k}的一个映射.图G的 k-全染色称为是正常的,如果满足相邻的或者相关联的两个元素染不同的颜色.类似的,可以定义图G的正常边染色.  令φ为图 G的正常k-边染色,用f(v)表示与点υ相关联的边在φ中所染颜色的加和,即(此处为公式省略).若对于图G中的任何一条边υυ∈E(G)都有f(u)≠ f(v),则称φ为图 G的邻和可区别k-边染色,使得图G存在邻和可区别k-边染色的最小整数k称为图G的邻和可区别边色数,记作x∑(G).类似的,若寸为图G的正常k-全染色,令g(v)=ψ(e)+∑e(>)v(e),若对任一条边ωυ∈E(G)都有g(u)≠ g(v),则称ψ为图G的邻和可区别k-全染色,使得图G存在邻和可区别k-全染色的最小整数k称为图G的邻和可区别全色数,记作Xυ∑(G).  如果对于图G的每一条边e,都给定一个颜色集合Le,那么这个映射L就称为图G的一个边列表.如果图G存在邻和可区别边染色φ使得任意边e∈E(G),都有φ(e)∈Le,则称图G是邻和可区别L-边可染的.对于图G的任意一个满足条件|Le|≥ k的边列表L,其中e∈ E(G)为G的任意一条边,如果G都是邻和可区别L-边可染的,那么就称图G是邻和可区别k-边可选择的.使得图G是邻和可区别k-边可选择的最小整数k称为图G的邻和可区别边可选择性,记作ch∑(G).类似的,可以给出图G的邻和可区别全可选择性ch"∑(G)的定义.由定义可知:ch"∑(G)≥X"∑(G),ch"∑(G)≥ X"∑(G).  本文主要考虑了若干图的邻和可区别边染色、邻和可区别边可选择性、邻和可区别全染色和邻和可区别全可选择性,并运用著名的组合零点定理与权转移方法得到以下主要结论.  定理1若图G为Halin图,当Δ(G)≠4时,X∑(G)≤Δ(G)+2;当Δ(G)≥6时, x∑(G)≤Δ(G)+1.  定理2若图G为正常2-退化图且Δ(G)≥4,则 ch"∑(G)≤Δ(G)+4.  定理3设图G是2-退化图,则x"∑(G)≤Δ(G)+3.并且,若Δ(G)≥5,则 x"∑(G)≤Δ(G)+2.  定理4设图G为最大度等于3的图且mad(G)<44/15,则ch"∑(G)≤6.  定理5设图G为最大度等于3的图且mad(G)<12/5,则ch"∑(G)≤5.  定理6设图G为最大度等于4的图且mad(G)<5/2,则ch"∑(G)≤6.  定理7设图G是最大度至少为11的图且mad(G)<5,则chn∑(G)≤Δ(G)+3.  定理8设图G是 d-退化图,若图G满足以下条件之一:  (1)d≤8且Δ(G)≥2d;  (2)d≥9且Δ(G)≥5/2d-5.  则ch"∑(G)≤Δ(G)+d+1.
其他文献
裂隙介质井流问题是裂隙介质水动力学中重要的内容之一。裂隙介质含水层中裂隙的不均匀分布,裂隙的方向不同和裂隙的粗糙程度的差异等都使得裂隙渗流具有各向异性性和非均质的
通过调查我们认为,当前和今后一个时期,加强国有企业党建工作必须坚持以“三个代表”重要思想为指导,全面贯彻党的十六大精神,坚持党对国有企业的政治领导不动摇,坚持企业党