Halin图的邻和可区别全染色
Neighbor sum distinguishing total coloring of Halin graph

摘要： 令［k］={1,2,…,k}, φ为图G的一个正常［k］-全染色。用f(v)表示点v及所有与其关联的边的颜色的加和,如果对任意边uv∈E(G),有f(u)≠f(v),则称该染色为图G的［k］-邻和可区别全染色。k的最小值称为图G的邻和可区别全色数,记为χ″Σ(G)。Pilsniak和Wozniak提出猜想:对任意简单图G,有χ″Σ(G)≤Δ(G)+3,其中Δ(G)表示图G的最大度。运用组合零点定理证明了该猜想对于任一Halin图成立。
Abstract: Let ［k］={1,2,…,k}, a mapping φ is a proper ［k］-total coloring of a graph G. Let f(v) denote the sum of the color of vertex v and the colors of the edges incident with v. A ［k］-neighbor sum distinguishing total coloring of G is a ［k］-total coloring of G such that for each edge uv∈E(G), f(u)≠f(v). Let χ″Σ(G) denote the smallest value k in such a coloring of G. Pilsniak and Wozniak conjectured that χ″Σ(G)≤Δ(G)+3 for any simple graph with maximum degree Δ(G). By using the Combinatorial Nullstellensatz, it shows that the conjecture holds for any Halin graph