A total [k]-coloring of a graph G is a mapping φ： V（G） U E（G） →{1, 2, ..., k} such that any two adjacent elements in V（G）UE（G） receive different colors. Let f（v） denote the sum of the colors of a vertex v...A total [k]-coloring of a graph G is a mapping φ： V（G） U E（G） →{1, 2, ..., k} such that any two adjacent elements in V（G）UE（G） receive different colors. Let f（v） denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total [k]-neighbor sum distinguishing-coloring of G is a total [k]-coloring of G such that for each edge uv E E（G）, f（u） ≠ f（v）. By tt [G, Xsd（ J, we denote the smallest value k in such a coloring of G. Pilniak and Woniak conjectured X＇sd（G） 〈 A（G） ＋ 3 for any simple graph with maximum degree A（G）. This conjecture has been proved for complete graphs, cycles, bipartite graphs, and subcubic graphs. In this paper, we prove that it also holds for Ka-minor free graphs. Furthermore, we show that if G is a Ka-minor flee graph with A（G） 〉 4, then ＂ Xnsd（G） 〈 A（G） ＋ 2. The bound A（G） ＋ 2 is sharp.展开更多
A k-total coloring of a graph G is a mapping φ： V（G） U E（G） → {1, 2,..., k} such that no two adjacent or incident elements in V（G） U E（G） receive the same color. Let f（v） denote the sum of the color on th...A k-total coloring of a graph G is a mapping φ： V（G） U E（G） → {1, 2,..., k} such that no two adjacent or incident elements in V（G） U E（G） receive the same color. Let f（v） denote the sum of the color on the vertex v and the colors on all edges incident with v. We say that ~ is a k-neighbor sum distinguishing total coloring of G if f（u） ≠ f（v） for each edge uv C E（G）. Denote X＂ （G） the smallest value k in such a coloring of G. Pilgniak and Wo/niak conjectured that for any simple graph with maximum degree △（G）, X＂（G） ≤ 3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for Ka-minor free graph G with △（G） ≥ 5, X＂（G） = △（G） ＋ 1 if G contains no two adjacent A-vertices, otherwise, X＂（G） = △（G） ＋ 2.展开更多
文摘A total [k]-coloring of a graph G is a mapping φ： V（G） U E（G） →{1, 2, ..., k} such that any two adjacent elements in V（G）UE（G） receive different colors. Let f（v） denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total [k]-neighbor sum distinguishing-coloring of G is a total [k]-coloring of G such that for each edge uv E E（G）, f（u） ≠ f（v）. By tt [G, Xsd（ J, we denote the smallest value k in such a coloring of G. Pilniak and Woniak conjectured X＇sd（G） 〈 A（G） ＋ 3 for any simple graph with maximum degree A（G）. This conjecture has been proved for complete graphs, cycles, bipartite graphs, and subcubic graphs. In this paper, we prove that it also holds for Ka-minor free graphs. Furthermore, we show that if G is a Ka-minor flee graph with A（G） 〉 4, then ＂ Xnsd（G） 〈 A（G） ＋ 2. The bound A（G） ＋ 2 is sharp.
文摘A k-total coloring of a graph G is a mapping φ： V（G） U E（G） → {1, 2,..., k} such that no two adjacent or incident elements in V（G） U E（G） receive the same color. Let f（v） denote the sum of the color on the vertex v and the colors on all edges incident with v. We say that ~ is a k-neighbor sum distinguishing total coloring of G if f（u） ≠ f（v） for each edge uv C E（G）. Denote X＂ （G） the smallest value k in such a coloring of G. Pilgniak and Wo/niak conjectured that for any simple graph with maximum degree △（G）, X＂（G） ≤ 3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for Ka-minor free graph G with △（G） ≥ 5, X＂（G） = △（G） ＋ 1 if G contains no two adjacent A-vertices, otherwise, X＂（G） = △（G） ＋ 2.
