An Upper Bound for the Adjacent Vertex-Distinguishing Total Chromatic Number of a Graph
Xin Liu · Journal of Mathematical Research and Exposition · 2009
Let G = (V,E) be a simple connected graph, and |V (G)| ≥ 2. Let f be a mapping from V (G) ∪ E(G) to {1,2,...,k}. If uv ∈ E(G),f(u) = f(v),f(u) = f(uv),f(v) = f(uv); uv, uw ∈ E(G)(v = w), f(uv) = f(uw); uv ∈ E(G) and u = v, C(u) = C(v), where C(u) = {f(u)} ∪ {f(uv)|uv ∈ E(G)}. Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G(k-AV DTC of G for short). The number min{k|k-AV DTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat(G). In this paper we prove that if (G) is at least a particular constant and δ ≥ 32√ln, then χat(G) ≤ (G) + 1026 + 2√ln.