单圈图的邻点全和可区别全染色

用结构分析法完整刻画单圈图U的邻点全和可区别全染色,并得到当U■C_(n)且n■0(mod 3)时,ftndiΣ(U)=Δ(U)+2;其他情况下,ftndiΣ(U)=Δ(U)+1.表明邻点全和可区别全染色猜想在任意单圈图上都成立.

子立方图的2-距离严格邻点可区别边染色

2-距离严格邻点可区别边染色是指图G有一个正常边染色,且任意2个距离为2的顶点的颜色集合互不包含.2-距离严格邻点可区别边色数是指使图G有一个2-距离严格邻点可区别边染色的最小颜色数值,记作χ′_(2-snd)(G).采用反证法证明了:若图G是子立方图,则χ′_(2-snd)(G)≤7.

三正则构造图的邻点全和可区别全染色

首先,根据Snark图的结构特点,构造基于双星和十字交叉形的两类三正则图;其次,利用穷染法和组合分析法研究四类三正则构造图的邻点全和可区别全染色问题,得到了它们的邻点全和可区别全色数均为2.

不含3-圈的平面图的弱邻点可区别边染色

弱邻点可区别边染色是指图G有一个正常边染色且任意2个相邻的最大度顶点的颜色集合不相等.使图G有一个弱邻点可区别边染色的最小颜色数值,被称为弱邻点可区别边色数,记作χ′_(a△)(G)证明了:若图G是不含3-圈的平面图,则有χ′_(a△)(G)≤max{9,△(G)+1}.

图的邻点全和可区别全染色

设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令φ(x)=f(x)+eЭx/∑f(e)+∑y∈N(x)/∑f(y),其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。

双圈图的邻点强可区别全染色

本文研究了双圈图的邻点强可区别全染色问题,并利用结构分析法给出了双圈图的邻点强可区别全色数的上界.即,当G是以∞-图为基图的双圈图时,则χ_(ast)(G)≤△(G)+2;其他χ_(ast)(G)≤△(G)+3.从而验证了张忠辅等提出的平面图的邻点强可区别全染色猜想在双圈图上是成立的.

若干倍图的邻点全和可区别全染色

为了进一步研究图的邻点全和可区别全染色问题,该文根据倍图的结构性,通过穷染法和染色算法,得到了路、圈、星、扇、轮、完全二部图以及树的倍图的邻点全和可区别全色数的精确值.

一类图的邻点被扩展和可区别全染色

根据完全多部图的特点,得到完全三部图和完全四部图的邻点被扩展和可区别全色数≤2,并证明Flandrin等(Discussiones Mathematicae Graph Theory,2017,37(1):29-37.)提出的NESDTC猜想对于完全三部图和完全四部图成立.最后对完全多部图的NESD问题作部分研究.

有向图的邻点可区别弧染色

研究了有向图的邻点可区别弧染色,证明了每个有向图D都有χ′_(-,+)(D)≤Δ*(D)+2。对于完全有向图,完全对称二部有向图和有向树,给出了邻点可区别弧染色数的更精确结果。

若干联图的邻点可区别I-全染色

利用函数构造法和数学归纳法,考虑图P_m∨S_n,F_m∨W_n和W_m∨W_n的邻点可区别I-全染色,给出了它们邻点可区别I-全色数.

若干路的冠图的邻点可区别V-全染色

根据路与完全图(星、扇、轮、路、圈)构造的冠图的结构性质,应用分析和构造函数法研究了邻点可区别V-全染色,得到了路与完全图(星、扇、轮、路、圈)构造的冠图的邻点可区别V-全色数.

关于θ-图的邻点可区别全染色

u,v两点间连三条内部不相交的路且至多有一条长度为1的图,称为θ-图.设G是阶至少为2的连通图,k是正整数,f是V(G)∪E(G)到{1,2,3,…,k}的映射,对任意u∈V(G),记C(u)={f(u)}∪{f(uv)｜uv∈E(G),v∈V(G)}.如果:1)对任意uv,vw∈E(G)u≠w,有f(uv)≠f(vw);2)对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);3)对任意uv∈E(G),有C(u)≠C(v),那么称f为G的k-邻点可区别全染色(简记为k-AVDTC),称min{k｜G有k-邻点可区别全染色}为G的邻点可区别全色数,记作χat(G).本文得到了θ-图的邻点可区别全染色.

几类弱积图的邻点可区别一般边染色

讨论了弱积图邻点可区别一般边染色,给出了P_(2n)×K_m,C_(2n)×C_(2m),C_(2n+1)×C_(2m+1),C_(2n+1)×K_m的邻点可区别一般边色数,得到了当G和H都无孤立边且色数均至少为3时,G×H邻点可区别一般边色数至少为3的结论.

一类2维广义格子图的邻点可区别全染色

定义一类2维广义格子图H2(G,n,m;k1,k2).且通过从图的结构出发,利用构造染色的方法,得到图H2(C5,n,m;5,5)的邻点可区别全色数.

关于若干倍图的关联邻点可区别全染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若f满足:(1)uv∈E(G),u≠v,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)uv∈E(G),C(u)≠C(v);其中C(u)={f(u)}∪{f(uv)uv∈E(G)}.则称f是G的一个关联邻点可区别全染色,所需的最少颜色数称为图G的关联邻点可区别全色数.给出了路、圈、星、扇、轮倍图的关联邻点可区别全色数.

P_m∨P_n的邻点可区别全染色

设G是阶数不小于2的简单连通图,G的k 正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶 点,其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为是G的邻点可区别全色数.得到了两条路的 联图的邻点可区别全色数.

若干倍图的邻点可区别均匀全染色

研究一些倍图的邻点可区别均匀全染色(AVDETC),利用构造法和匹配法给出了偶阶完全图、偶阶圈、路、星和轮的倍图的邻点可区别均匀全色数,并验证了它们满足邻点可区别均匀全染色猜想(AVDETCC).

关于邻点可区别全染色的几个新结果

邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同.顶点v的色集是v的颜色及其与v关联的所有边的颜色.我们给出了几类特殊图的邻点可区别全色数.

完全图的倍图的邻点可区别全染色

讨论D(Kn)的邻点可区别全染色问题,给出并证明D(Kn)的邻点可区别全色数χat(D(Kn))=2n.

多重Mycielski图的邻点可区别全染色

给出了一个简单图G的k重Mycielski图Mk(G)(其中k为正整数)的邻点可区别全色数的上界,得到了圈、星、轮、扇的k重Mycielski图的邻点可区别全色数.