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

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

mC12的点被多重集可区别的I-全染色和VI-全染色

通过构造以多重色集合和空集为元素的矩阵,应用组合分析法及构造具体染色的方法,得到了mC12的点被多重色集合可区别的I-全染色和VI-全染色的全色数及最优染色方案。

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

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

随机图的邻点可区别VI-均匀全染色算法

邻点可区别VI-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类(点或边)的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别VI-均匀全色数。提出了一种针对随机图的邻点可区别VI-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别VI-均匀全色数。

若干图的邻点可区别的I-全染色和邻点可区别的I-均匀全染色

图G的一个邻点可区别的I-均匀全染色是指对图G的一个邻点可区别的I-全染色f,若f还满足任意两个色类(点和边)的颜色个数最大相差为1.对图G进行邻点可区别的I-均匀全染色所用颜色的最小数量称为图G的邻点可区别I-均匀全色数.文章通过函数构造法,研究并确定了路、圈、星、扇和轮的平方图的邻点可区别I-均匀全色数并验证了其满足猜想:χatei(G)≤Δ(G)+2.最后给出了C5∨Wn的邻点可区别I-全色数.

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

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

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

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

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

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

若干Mycielski图邻点可区别Ⅰ-均匀全染色

图G的一个邻点可区别Ⅰ-均匀全染色是指对图G的邻点可区别的一个Ⅰ-全染色f,若f还满足||T_i|-|T_j||≤1(i≠j),其中T_i=V_i∪E_i={v|v∈V(G),f(v)=i}∪{e|e∈E(G),f(e)=i},则称f为图G的一个邻点可区别Ⅰ-均匀全染色,而图G的邻点可区别Ⅰ-均匀全染色中所用的最少颜色数称为图G的邻点可区别Ⅰ-均匀全色数.通过函数构造法,得到了M(Pn)、M(Cn)、M(Sn)的邻点可区别Ⅰ-均匀全色数,并且满足猜想.

冠图C_m·C_n与C_m·K_n的邻点可区别I-全染色

为了寻找一般图的邻点可区别I-全染色法,应用构染色函数法给出了冠图Cm·Cn和Cm·Kn的邻点可区别I-全染色,得到了其邻点可区别I-全色数,进一步验证了邻点可区别I-全染色的猜想.

P_m∨F_n及P_m∨W_n的邻点可区别I-全染色

图G的I-全染色是指对图G的顶点和边染色,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻顶点u,v的色集合C(u)≠C(v),这里C(u)={f(u)}∪{f(uv)|uv∈E(G)}.而图G的邻点可区别I-全染色中所用的最少色数称为图G的邻点可区别I-全色数.讨论路与扇的联图Pm∨Fn、路与轮联图Pm∨Wn的邻点可区别I-全染色问题,根据这类图的结构性质运用色构造法给出它们的邻点可区别I-全染色方法,从而有效地确定其邻点可区别I-全色数.

路、扇及星的Mycielski图的邻点可区别I-全染色

研究了Pn,Fn和Sn图的Mycielski图的邻点可区别的I-全染色.图G的邻点可区别的I-全染色是从G的点边集V(G)∪E(G)到色集{1,2,…,k}的一个映射f,满足:任意uv∈E(G),u≠v,有f(u)≠f(v);任意uv,uw∈E(G),v≠w,有f(uv)≠f(uw);任意uv∈E(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.最小的k值称为图G的邻点可区别的I-全色数,记作χiat(G).根据图M(Pn),M(Fn)和M(Sn)的构造特征,利用构造函数法,构造了一个从点边集V(G)∪E(G)到色集合{1,2,…,k}的函数,给出了一种染色方案,得到了M(Pn),M(Fn)和M(Sn)图的邻点可区别的I-全色数,并且满足猜想.

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

如果图G的一个正常全染色满足相邻点的色集合不同,且任意两种颜色所染的元素的数目之差的绝对值不超过1,则称为邻点可区别均匀全染色(AVDETC),其所用的最少颜色数称为邻点可区别均匀全色数。本文研究了路、圈、星、扇的Mycielski图的邻点可区别均匀全染色,利用构造法和匹配法给出了它们的邻点可区别全色数的确切值,验证了它们满足邻点可区别均匀全染色猜想(AVDETCC)。

图C_(n,m)的邻点可区别均匀E-全染色

针对图的邻点可区别均匀E-全染色问题,用结构分析的方法和穷举法研究图Cn,m(n≥3,m≥1)的邻点可区别均匀E-全染色问题,得到它们的邻点可区别均匀E-全色数,并验证结果的有效性.

关于联图P_n∨C_n的邻点可区别的均匀全染色

一个图G的全染色被称为邻点可区别的如果满足图G中任意两个相邻点所关联的元素所染的色的集合不同.一个图的邻点可区别的全染色被称为均匀的如果满足任意两色所染元素的数目之差的绝对值不超过1.本文研究了联图P_n∨C_n的邻点可区别的均匀全染色并证明它满足邻点可区别的均匀全染色猜想.

关于一类二部图的均匀邻点可区别全染色

若图的邻点可区别全染色的各色所染元素数之差不超过1,则称该染色法为图的均匀邻点可区别全染色,而所用的最少颜色数称为该图的均匀邻点可区别全色数.本文给出了一类二部图的均匀邻点可区别全染色数.

图P_n□C_m的邻点可区别I-全染色

通过对图Pn□Cm的积图的邻点可区别全染色研究,来进一步验证邻点可区别全染色的猜想.应用构造具体染色的方法给出了图Pn□Cm的积图的邻点可区别全染色.得到了图Pn□Cm的积图的邻点可区别全染色的色数.

关于路和路的联图的邻点可区别的均匀全染色

一个图G的全染色被称为邻点可区别的,如果满足图G中任意两个相邻点所关联的元素所染的色的集合不同.一个图的邻点可区别的全染色被称为均匀的,如果满足任意两色所染元素的数目之差的绝对值不超过1.本文研究了联图P_n■P_n的邻点可区别的均匀全染色并证明它满足邻点可区别的均匀全染色猜想.

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

研究了冠图SnPm,PnSm,SnCm和CnSm的邻点可区别I-全染色问题.根据这些冠图的结构特征,构造了一个从集合V(G)∪E(G)到色集合{1,2,…,k}的函数,给出了一种染色方案,得到了它们的邻点可区别的I-全色数.

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

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