广义Mycielski图M_n(P_m^2)的邻点可区别的非正常全染色

文中讨论了广义Mycielski图M_n(P_m^2)的邻点可区别非正常全染色,并给出了相应色数.

两类正则图的邻点全和可区别全染色

设f:V(G)∪E(G)→[1,k]是图G的一个非正常k-全染色.令φ(x)=f(x)+∑e∈xf(e)+∑y∈N(x)f(y),其中N(x)={y∈V(G)|xy∈E(G)}.对任意的边uv∈E(G),如果有φ(u)≠φ(v)成立,则称f是图G的一个邻点全和可区别(简记NFSD)k-全染色.图G的邻点全和可区别全染色中最小的k值称为G的邻点全和可区别全色数,记为fgndi_(Σ)(G).通过构造染色函数法,确定了广义Petersen图和循环图的邻点全和可区别全色数.

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

进一步研究了平方图的邻点全和可区别非正常全染色问题:利用平方图的结构构造了路、圈、毛毛虫、广义星以及最大度为3且不含2度点的树的平方图,通过组合分析法得到上述5类平方图的邻点全和可区别非正常全色数。

几类笛卡尔乘积图的邻点全和可区别全染色

设f:V(G)∪E(G)→[k]是图G的一个非正常的k-全染色,令权重(x)=f(x)+∑x∈ef(e)+∑y∈N(x)f(y),其中,N(x)={y∈V(G)|xy∈E(G)}对任意的边uv∈E(G),如果有(u)≠(v)成立,则称f为图G的一个邻点全和可区别非正常k-全染色。图G的邻点全和可区别非正常全染色中最少的颜色数k叫做G的邻点全和可区别全色数,记为fgndi∑(G)。文章研究了几类笛卡尔乘积图G×H的邻点全和可区别非正常全染色,得到fgndi∑(Pm×Pn)=fgndi∑(Pm×Cn)=fgndi∑(Cm×Cn)=fgndi∑(Pm×Kn)=fgndi∑(Cm×Kn)=2。结果表明,邻点全和可区别全染色猜想对上述几类笛卡尔乘积图均成立。

图C_m^2×S_n与C_m^2×F_n与的gndt-染色

单图G的邻点可区别的非正常全染色是指图的任意相邻两顶点的色集合都不同的全染色.所谓顶点的色集合是指顶点自身的颜色及与其关联的所有边的颜色的集合.文中讨论了笛卡儿积图C_m^2×S_n和C_m^2×F_n的邻点可区别非正常全染色,并给出了相应色数.

关于图的邻和可区别全染色的新方法

给出树的邻和可区别2-全染色方案,并结合三正则图最小消圈集的独立性以及消圈子图的无圈性,较为简洁地证明三正则图的邻和可区别全色数满足1-2猜想。进一步利用独立消圈集法确定r-正则图、Halin图以及路与路的笛卡尔乘积图的邻和可区别全色数。