zbMATH — the first resource for mathematics

Concise proofs for adjacent vertex-distinguishing total colorings. (English) Zbl 1221.05143
Summary: Let \(G=(V,E)\) be a graph and \(f:(V \cup E)\rightarrow [k]\) be a proper total \(k\)-coloring of \(G\). We say that \(f\) is an adjacent vertex- distinguishing total coloring if for any two adjacent vertices, the set of colors appearing on the vertex and incident edges are different. We call the smallest \(k\) for which such a coloring of \(G\) exists the adjacent vertex-distinguishing total chromatic number, and denote it by \(\chi at(G)\). Here we provide short proofs for an upper bound on the adjacent vertex-distinguishing total chromatic number of graphs of maximum degree three, and the exact values of \(\chi at(G)\) when \(G\) is a complete graph or a cycle.

05C15 Coloring of graphs and hypergraphs
PDF BibTeX Cite
Full Text: DOI
[1] Burris, A.; Schelp, R., Vertex-distinguishing proper edge-colorings, Journal of graph theory, 26, 2, 73-82, (1997) · Zbl 0886.05068
[2] Bazgan, C.; Harkat-Benhamdine, A.; Li, H.; Woźniak, M., On the vertex-distinguishing proper edge-coloring of graphs, Journal of combinatorial theory, series B, 75, 2, 288-301, (1999) · Zbl 0932.05036
[3] Balister, P.; Bollobás, B.; Schelp, R., Vertex distinguishing colorings of graphs with \(\Delta(G) = 2\), Discrete mathematics, 252, 2, 17-29, (2002) · Zbl 1005.05019
[4] Zhang, Z.; Liu, L.; Wang, J., Adjacent strong edge coloring of graphs, Applied mathematics letters, 15, 5, 623-626, (2002) · Zbl 1008.05050
[5] Zhang, Z.; Chen, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex-distinguishing total coloring of graphs, Science in China series A mathematics, 48, 289-299, (2005) · Zbl 1080.05036
[6] Wang, H., On the adjacent vertex-distinguishing total chromatic numbers of the graphs with \(\Delta(G) = 3\), Journal of combinatorial optimization, 14, 87-109, (2007) · Zbl 1125.05043
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.