The adjacent vertex distinguishing total coloring of planar graphs. (English) Zbl 1319.90076

Wang, Weifan; Huang, Danjun

J. Comb. Optim. 27, No. 2, 379-396 (2014).

Summary: An adjacent vertex distinguishing total coloring of a graph \(G\) is a proper total coloring of \(G\) such that any pair of adjacent vertices have distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of \(G\) is denoted by \(\chi''_{a}(G)\).
In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of planar graphs \(G\) with large maximum degree \(\varDelta \) by showing that if \(\varDelta \geq 14\), then \(\varDelta+1\leq \chi''_{a}(G)\leq \varDelta+2\), and \(\chi''_{a}(G)=\varDelta+2\) if and only if \(G\) contains two adjacent vertices of maximum degree.

MSC:

90C35	Programming involving graphs or networks
05C15	Coloring of graphs and hypergraphs

Keywords:

adjacent vertex distinguishing total coloring; planar graph; maximum degree

References:

[1]	Appel K, Haken W (1976) Every planar graph map is four colorable. Bull Am Math Soc 82:711-712 · Zbl 0331.05106
[2]	Chen X (2008) On the adjacent vertex distinguishing total coloring numbers of graphs with Δ=3. Discrete Math 308:4003-4007 · Zbl 1203.05052
[3]	Huang D, Wang W (2012) Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree. Sci Sin Math 42:151-164 (in Chinese) · Zbl 1488.05182
[4]	Hulgan J (2009) Concise proofs for adjacent vertex-distinguishing total colorings. Discrete Math 309:2548-2550 · Zbl 1221.05143
[5]	Vizing V (1964) On an estimate of the chromatic index of a p-graph. Diskret Anal 3:25-30
[6]	Wang H (2007) On the adjacent vertex distinguishing total chromatic number of the graphs with Δ(G)=3. J Comb Optim 14:87-109 · Zbl 1125.05043
[7]	Wang W, Wang Y (2008) Adjacent vertex distinguishing total coloring of graphs with lower average degree. Taiwan J Math 12:979-990 · Zbl 1168.05023
[8]	Wang W, Wang P (2009) Adjacent vertex distinguishing total coloring of K4-minor free graphs. Sci China Ser A 39:1462-1472 (in Chinese)
[9]	Wang Y, Wang W (2010) Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim 19:123-133 · Zbl 1216.05039
[10]	Zhang Z, Chen X, Li J, Yao B, Lu X, Wang J (2005) On adjacent-vertex-distinguishing total coloring of graphs. Sci China Ser A 48:289-299 · Zbl 1080.05036