page_title: Adjacent-vertex-distinguishing-total coloring
hierarchical_section_title: Adjacent-vertex-distinguishing-total coloring
context_page_description: In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that:
  . no adjacent vertices have the same color;
  . no adjacent edges have the same color; and
  . no edge and its endvertices are assigned the same color.
  In 2005, Zhang et al. added a restriction to the definition of total coloring and proposed a new type of coloring defined as follows.
  Let G = be a simple graph endowed with a total coloring φ, and let u be a vertex of G. The set of colors that occurs in the vertex u is defined as C = {φ} ∪ {φ | uv ∈ E}. Two vertices u, v ∈ V are distinguishable if their color-sets are distinct, i.e., C ≠ C.
  In graph theory, a total coloring is an adjacent-vertex-distinguishing-total-coloring if it has the following additional property:
  . for every two adjacent vertices u, v of a graph G, their colors-sets are distinct from each other, i.e., C ≠ C.
  The adjacent-vertex-distinguishing-total-chromatic number χₐₜ of a graph G is the fewest colors needed in an AVD-total-coloring of G.
context_section_description: In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that:
  (1). no adjacent vertices have the same color;
  (2). no adjacent edges have the same color; and
  (3). no edge and its endvertices are assigned the same color.
  In 2005, Zhang et al. added a restriction to the definition of total coloring and proposed a new type of coloring defined as follows.
  Let G = (V,E) be a simple graph endowed with a total coloring φ, and let u be a vertex of G. The set of colors that occurs in the vertex u is defined as C(u) = {φ(u)} ∪ {φ(uv) | uv ∈ E(G)}. Two vertices u,v ∈ V(G) are distinguishable if their color-sets are distinct, i.e., C(u) ≠ C(v).
  In graph theory, a total coloring is an adjacent-vertex-distinguishing-total-coloring (AVD-total-coloring) if it has the following additional property:
  (4). for every two adjacent vertices u,v of a graph G, their colors-sets are distinct from each other, i.e., C(u) ≠ C(v).
  The adjacent-vertex-distinguishing-total-chromatic number χₐₜ(G) of a graph G is the fewest colors needed in an AVD-total-coloring of G.
  The following lower bound for the AVD-total chromatic number can be obtained from the definition of AVD-total-coloring: If a simple graph G has two adjacent vertices of maximum degree, then χₐₜ(G) ≥ Δ(G) + 2. Otherwise, if a simple graph G does not have two adjacent vertices of maximum degree, then χₐₜ(G) ≥ Δ(G) + 1.
  In 2005, Zhang et al. determined the AVD-total-chromatic number for some classes of graphs, and based in their results they conjectured the following.
  AVD-Total-Coloring Conjecture. (Zhang et al.)
  χₐₜ(G) ≤ Δ(G) + 3.
  The AVD-Total-Coloring Conjecture is known to hold for some classes of graphs, such as complete graphs, graphs with Δ=3, and all bipartite graphs.
  In 2012, Huang et al. showed that χₐₜ(G) ≤ 2Δ(G)
  for any simple graph G with maximum degree Δ(G) > 2.
  In 2014, Papaioannou and Raftopoulou described an algorithmic procedure that gives a 
  7-AVD-total-colouring for any 4-regular graph.
caption: A proper AVD-total-coloring of the complete graph K4 with 5 colors, the minimum number possible.