کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646744 | 1342312 | 2016 | 4 صفحه PDF | دانلود رایگان |
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).
Journal: Discrete Mathematics - Volume 339, Issue 10, 6 October 2016, Pages 2446–2449