Article ID Journal Published Year Pages File Type
4646744 Discrete Mathematics 2016 4 Pages PDF
Abstract

Let ϕϕ be a proper total coloring of GG. We use Cϕ(v)={ϕ(v)}∪{ϕ(uv)∣uv∈E(G)}Cϕ(v)={ϕ(v)}∪{ϕ(uv)∣uv∈E(G)} to denote the set of colors assigned to a vertex vv and those edges incident with vv. An adjacent vertex distinguishing total coloring of a graph GG is a proper total coloring of GG such that Cϕ(u)≠Cϕ(v)Cϕ(u)≠Cϕ(v) for any uv∈E(G)uv∈E(G). The minimum number of colors required for an adjacent vertex distinguishing total coloring of GG is denoted by χa″(G). In this paper we show that if GG is a 2-degenerate graph, then χa″(G)≤max{Δ(G)+2,6}. Moreover, we also show that when Δ≥5Δ≥5, χa″(G)=Δ(G)+2 if and only if GG contains two adjacent vertices of maximum degree. Our results imply the results on outerplanar graphs (Wang and Wang, 2010), K4K4-minor free graphs (Wang and Wang, 2009) and graphs with maximum average degree less than 3 (Wang and Wang, 2008).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,