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

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

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

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

一类P_m×C_n图的邻点强可区别全染色

图的一个正常的全染色满足相邻点的点及其关联边染色的色集不同时,称为邻点强可区别全染色,其所用最少染色数称为邻点强可区别全色数。经证明得到了一类积图Pm×Cn的邻点强可区别色数。

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

设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。

P_n×P_m的邻点强可区别的全染色

讨论路的笛卡尔积的邻点可区别的全染色问题,给出路的笛卡尔积Pn×Pm的邻点强可区别的全色数为χast(Pn×Pm)=5 n=2,m≥2或m=n=36 min{n。

图的邻点强可区别的Ⅵ-全染色

提出了图的邻点强可区别的Ⅵ-全染色的概念,即:AST-Ⅵ-染色,并讨论了它的基本性质及路、圈、完全二部图、完全图、树、3-正则图的邻点强可区别的Ⅵ-全色数.

中间图的邻点强可区别全染色

通过分类讨论、归纳探究,在图的点边集合与色集合间构造了一种一一对应关系来研究路和圈的中间图的邻点强可区别全染色,并得到了它们的邻点强可区别全染色数.

D(p_n)图的邻点强可区别全染色

设f为用k色时G的正常全染色法,对任意的边uv∈E(G),其端点的色集合满足C(u)≠C(v),其中C(u)={f(u)}∪{f(v)|uv∈E(G)}∪{f(uv)|uv∈E(G)},则称f是G的k邻点强可区别的全染色法(简记作k-AVSDTC),且称ast(G)=min{k|G的所有k-AVSDTC}为G的邻点强可区别全色数.本文得到D(pn)图的邻点强可区别全色数,其中pn为n阶路.

P_n×P_m图的邻点可区别全染色和邻点强可区别全染色

对Pn×Pm图的邻点可区别全染色和邻点强可区别全染色问题进行了探讨,给出了染色数公式Xat(Pn×Pm)={4 n=m=2 5 n=2 m≥3,ast(pn×pm)=6 n≥3 n≥3{5 n=m=25 n=2 m≥3 6 n≥3

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

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

C_(3m)×C_(3n)、C_(4m)×C_(4n)的邻点强可区别全染色及全色数

给出了图C3m×C3n、C4m×C4n的一种全染色方法,并证明了该染色是邻点强可区别的,从而得到了C3m×C3n、C4m×C4n的邻点强可区别的全色数:aχst(C3m×C3n)=6、aχst(C4m×C4n)=6.此结果尚未见其他文件报道.

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

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

路和圈的笛卡尔积的邻点强可区别全染色

本文介绍了部分特殊图类的笛卡尔积图的邻点可区别全染色的有关重要结论,并在此基础上讨论n阶路和n阶圈的笛卡尔积Pn×Cn的邻点强可区别全染色,得到了n阶路和n阶圈的笛卡尔积Pn×Cn的邻点强可区别全然色数χast()Pn×Cn=6。

齿轮图的邻点强可区别的全染色

利用穷举法和组合分析法讨论了齿轮图Wn(n≥3且n≠4)的邻点强可区别的全染色,通过构造具体染色得到了齿轮图Wn(n≥3且n≠4)的邻点强可区别的全色数。

几个笛卡儿积图的邻点强可区别的EI-全染色

给出了笛卡儿积图Pm×Sn,Pm×Fn,Pm×Pn,Pm×Wn,Pm×Cn的邻点强可区别的EI-全色数.

路的平方及立方的邻点强可区别E-全染色

对简单图G(V,E),存在一个正整数k,使得映射f:V(G)∪E(G)→{1,2,…,k},如果uv∈E(G),有f(u)≠f(v),f(u)≠f(uv)且C(u)≠C(v),其中:C(u)={f(u)}∪{f(uv),f(v)|uv∈E(G),v∈V(G)},则称f是图G的邻点强可区别E-全染色,且称最小的数k为图G的邻点强可区别E-全色数.本文应用构造染色法研究了有关路的平方及立方图的邻点强可区别E-全染色,并得出其邻点强可区别E-全色数.

两类Mycielski图的邻点强可区别E-全染色

应用反证法和构造染色函数法研究了距离为三的图F_n和W_n的k重Mycielski图的邻点强可区别E-全染色,并得出了其邻点强可区别E-全色数.

两类特殊图的邻点强可区别E-全染色

对简单图G(V,E),存在一个正整数k,使得映射f:V(G)∪E(G)→{1,2,…,k},如果坌uv∈E(G),有f(u)≠f(v),f(u)≠f(uv)且C(u)≠C(v),其中C(u)={f(u)}∪{f(uv),f(v)|uv∈E(G),v∈V(G)},则称f是图G的邻点强可区别E-全染色,且称最小的数k为图G的邻点强可区别E-全色数。在此基础上应用构造染色法研究了图F_m×F_n、M(P_n^2)的邻点强可区别E-全染色,并得出了其邻点强可区别E-全色数。

扇和轮的邻点强可区别全染色

研究了扇和轮的邻点强可区别全染色并得到了它们的邻点强可区别全色数.

两类特殊图的邻点强可区别E-全染色

邻点强可区别全染色的定义弱化其中的一个条件,即相邻边可以染同色时,则可得到邻点强可区别E-全热色的概念.利用反证法和构造函数染色法得出距离为2的扇图和轮图的K重Mycielski图的邻点强可区别E-全染色以及其全色数.