Adjacent vertex distinguishing total colorings of 2-degenerate graphs

作者：Miao, Zhengke; Shi, Rui; Hu, Xiaolan^*; Luo, Rong

来源：Discrete Mathematics, 2016, 339(10): 2446-2449.

DOI：10.1016/j.disc.2016.03.019

• Adjacent vertex distinguishing total coloring
• 2-degenerate graph
• Maximum degree

Let phi be a proper total coloring of G. We use C-phi(v) = {phi(v)} U {phi(uv) vertical bar uv epsilon E(G)} to denote the set of colors assigned to a vertex v and those edges incident with v. An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that C-phi(u) not equal C-phi(v) for any uv epsilon E(G). The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by x(a)''(G). In this paper we show that if G is a 2-degenerate graph, then x(a)'' (G) <= max{Delta(G) + 2, 6}. Moreover, we also show that when Delta >= 5, x(a)''(G) = Delta(G) + 2 if and only if G contains two adjacent vertices of maximum degree. Our results imply the results on outerplanar graphs (Wang and Wang, 2010), K-4-minor free graphs (Wang and Wang, 2009) and graphs with maximum average degree less than 3 (Wang and Wang, 2008).

• 出版日期2016-10-6
• 单位华中师范大学