×

zbMATH — the first resource for mathematics

The adjacent vertex distinguishing total coloring of planar graphs. (English) Zbl 1319.90076
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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel, K; Haken, W, Every planar graph map is four colorable, Bull Am Math Soc, 82, 711-712, (1976) · Zbl 0331.05106
[2] Chen, X, On the adjacent vertex distinguishing total coloring numbers of graphs with \(Δ\)=3, Discrete Math, 308, 4003-4007, (2008) · Zbl 1203.05052
[3] Huang, D; Wang, W, Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, Sci Sin Math, 42, 151-164, (2012)
[4] Hulgan, J, Concise proofs for adjacent vertex-distinguishing total colorings, Discrete Math, 309, 2548-2550, (2009) · Zbl 1221.05143
[5] Vizing, V, On an estimate of the chromatic index of a \(p\)-graph, Diskret Anal, 3, 25-30, (1964)
[6] Wang, H, On the adjacent vertex distinguishing total chromatic number of the graphs with \(Δ\)(\(G\))=3, J Comb Optim, 14, 87-109, (2007) · Zbl 1125.05043
[7] Wang, W; Wang, Y, Adjacent vertex distinguishing total coloring of graphs with lower average degree, Taiwan J Math, 12, 979-990, (2008) · Zbl 1168.05023
[8] Wang, W; Wang, P, Adjacent vertex distinguishing total coloring of \(K\)_{4}-minor free graphs, Sci China Ser A, 39, 1462-1472, (2009)
[9] Wang, Y; Wang, W, Adjacent vertex distinguishing total colorings of outerplanar graphs, J Comb Optim, 19, 123-133, (2010) · Zbl 1216.05039
[10] Zhang, Z; Chen, X; Li, J; Yao, B; Lu, X; Wang, J, On adjacent-vertex-distinguishing total coloring of graphs, Sci China Ser A, 48, 289-299, (2005) · Zbl 1080.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.