仙人掌图的邻点被扩展和可区别全染色

设G为简单图.G的全k-染色是指k种颜色1,2,…,k对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称w(x)∑/e■xc(e)+∑/y∈N(x)为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点被扩展和可区别(简记为NESD),如果w(x)≠w(y),其中xy∈E(G).使得图G存在NESD全k-染色的最小值k被称为图G的邻点被扩展和可区别全色数,简记为egndi∑(G).本文利用数学归纳法探讨了仙人掌图的邻点被扩展和可区别全染色,并证明了这类图的邻点被扩展和可区别全色数不超过2.该结论说明Flandrin等人提出的NESDTC猜想对于仙人掌图是成立的.

The neighbor expanded sum distinguishing total colorings of cactus graphs

Let G be a simple graph.A total k-coloring of G is an assignment of k colors1,2,…,k to all vertices and edges of G.For x ∈ V(G)and N(x)={y∈V(G)|xy ∈E(G)},the value w(x)∑/e■xc(e)+∑/y∈N(x) c(y)is called the expanded sum atx,where c is a total k-coloring of G.A total k-coloring c of G is called the neighbor expanded sum distinguishing(NESD for short)if w(x)≠w(y),whenever xy ∈ E(G).The minimum number k of an NESD total k-coloring of G is called the neighbor expanded sum distinguishing total chromatic number of G and denoted by egndi∑(G).The neighbor expanded sum distinguishing total colorings of cactus graphs are discussed in this paper by using the method of mathematical induction,and prove that the neighbor expanded sum distinguishing total chromatic number of any cactus graph is less than or equal to 2.This result illustrates that the NESDTC conjecture proposed by Flandrin,et al is true for cactus graphs.