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

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

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

设G是简单连通图,G的k-正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,称f为G的k-邻点可区别全染色.这样的k中最小者称为G的邻点可区别全色数.本文考虑了图的中间图的邻点可区别全色数,并确定了路、圈、星图和扇图的中间图的邻点可区别全色数.

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

设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。结果表明,邻点全和可区别全染色猜想对上述几类笛卡尔乘积图均成立。

关于图邻点可区别上界的一点注(英文)

设G为一简单连通图 .它的一个正常全染色叫做一个邻点可区别的全染色 .如果满足 :对G的任意两个顶点u ,v,都有染点u以及与u相连的边所形成的色集与染点v以及与v相连的边所形成的色集不同 .如果一个邻点可区别的全染色需要的色数为κ ,则把这个染色叫做k 邻点可区别的全染色 (简记为k AVDTC) .对图G ,记χ′at(G) =min{k｜G有一个k AVDTC} ,称 χ′at(G)为图G的邻点可区别的全色数 .

Adjacent-Vertex-Distinguishing Total Chromatic Number of P_m×K_n

Let G be a simple graph. Let f be a mapping from V（G） U E（G） to {1, 2,..., k}. Let Cf（v） = {f（v）} U {f（vw）｜w ∈ V（G）,vw ∈ E（G）} for every v ∈ V（G）. If f is a k-propertotal-coloring, and if Cf（u） ≠ Cf（v） for uv ∈ V（G）,uv E E（G）, then f is called k-adjacentvertex-distinguishing total coloring of G（k-AVDTC of G for short）. Let χat（G） = min{k｜G has a k-adjacent-vertex-distinguishing total coloring}. Then χat（G） is called the adjacent-vertex-distinguishing total chromatic number. The adjacent-vertex-distinguishing total chromatic number on the Cartesion product of path Pm and complete graph Kn is obtained.