论文部分内容阅读
本文所考虑的图均为有限、无向、简单图,分别用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.