Adjacent vertex distinguishing total coloring of graphs with lower average degree

作者：Wang Weifan^*; Wang Yiqiao

来源：Taiwanese Journal of Mathematics, 2008, 12(4): 979-990.

• adjacent vertex distinguishing total coloring
• maximum average degree
• planar graph
• girth
• discharging method

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by chi(a)''(G). Let mad(G) and Delta(G) denote the maximum average degree and the maximum degree of a graph G, respectively.
In this paper, we prove the following results: (1) If G is a graph with mad(G) < 3 and Delta(G) >= 5, then Delta(G) + 1 <= chi(a)''(G) <= Delta(G) + 2, and chi(a)''(G) = Delta(G) + 2 if and only if G contains two adjacent vertices of maximum degree; (2) If G is a graph with mad(G) < 3 and Delta(G) <= 4, then chi(a)''(G) <= 6; (3) If G is a graph with mad(G) < and Delta(G) <= 3, then chi(a)''(G) <= 5.

• 出版日期2008-7
• 单位浙江师范大学