Adjacent vertex distinguishing total coloring;
Planar graph;
Maximum degree;
DISTINGUISHING TOTAL COLORINGS;
MAP;
D O I:
10.1007/s10878-016-9995-x
中图分类号:
TP39 [计算机的应用];
学科分类号:
081203 ;
0835 ;
摘要:
A (proper) total-k-coloring of a graph G is a mapping phi : V(G) boolean OR E(G) bar right arrow. {1, 2,..., k} such that any two adjacent elements in V(G) boolean OR E(G) receive different colors. Let C(v) denote the set of the color of a vertex v and the colors of all incident edges of v. A total-k-adjacent vertex distinguishing-coloring of G is a total-k-coloring of G such that for each edge uv is an element of E(G), C(u) not equal C(v). We denote the smallest value k in such a coloring of G by chi ''(a)(G). It is known that chi ''(a)(G) <= Delta (G) + 3 for any planar graph with Delta (G) >= 11. In this paper, we show that if G is a planar graph with Delta (G) >= 10, then chi ''(a)(G) <= Delta (G) + 3. Our approach is based on Combinatorial Nullstellensatz and the discharging method.
机构:
Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, IsraelTel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel
机构:
Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, IsraelTel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel