Neighbor sum distinguishing total colorings of K4-minor free graphs
Neighbor sum distinguishing total colorings of K4-minor free graphs
复制标题
DOI：
10.1007/s11464-013-0322-x
复制
发表时间：
2013-08
影响因子：
--
通讯作者：
Hualong Li;Bingqiang Liu;G. Wang
中科院分区：
文献类型：
--
作者：
Hualong Li;Bingqiang Liu;G. Wang
一个图的总[k]着色是一个映射φ:V(G)∪E(G)→{1,2，…，k}使得任意两个相邻的元素inV(G)∪E(G)得到不同的颜色。令(v)表示顶点的颜色与v的所有入射边的颜色之和。区分gis着色的总[k]邻和，G的总[k]着色，使得对于每条边v∈E(G),f(u)≠f(v)。通过χnsd″，我们表示g的这种着色中的最小值。Pilśniak和Woźniak conjecturedχnsd″(G)≤Δ(G)+3，适用于任何最大度为Δ(G)的简单图。这个猜想已经在完全图、环、二部图和次三次图中得到了证明。在本文中，我们证明了它也持有forK4-minor free图。此外，我们显示ifGis的ak4次要自由图与Δ(G)或或或或或或或或或或或或大于或等于″(G)≤Δ(G) + 2。Δ(G) + 2的边界很明显。
A total [k]-coloring of a graphGis a mappingϕ:V(G) ∪E(G) → {1, 2, …,k} such that any two adjacent elements inV(G)∪E(G) receive different colors. Letf(v) denote the sum of the colors of a vertexvand the colors of all incident edges ofv. A total [k]-neighbor sum distinguishing-coloring ofGis a total [k]-coloring ofGsuch that for each edgeuv ∈ E(G),f(u) ≠f(v). Byχnsd″, we denote the smallest valuekin such a coloring ofG. Pilśniak and Woźniak conjecturedχnsd″(G) ⩽ Δ(G)+3 for any simple graph with maximum degree Δ(G). This conjecture has been proved for complete graphs, cycles, bipartite graphs, and subcubic graphs. In this paper, we prove that it also holds forK4-minor free graphs. Furthermore, we show that ifGis aK4-minor free graph with Δ(G) ⩾ 4, thengcnsd″(G) ⩽ Δ(G) + 2. The bound Δ(G) + 2 is sharp.