Adjacent-vertex-distinguishing-total coloring explained

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.[1] 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) = ∪ . 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 χat(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 χat(G) ≥ Δ(G) + 2.[2] Otherwise, if a simple graph G does not have two adjacent vertices of maximum degree, then χat(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.[3])

χat(G) ≤ Δ(G) + 3.

The AVD-Total-Coloring Conjecture is known to hold for some classes of graphs, such as complete graphs,[4] graphs with Δ=3,[5] [6] and all bipartite graphs.[7]

In 2012, Huang et al.[8] showed that χat(G) ≤ 2Δ(G)for any simple graph G with maximum degree Δ(G) > 2.In 2014, Papaioannou and Raftopoulou[9] described an algorithmic procedure that gives a 7-AVD-total-colouring for any 4-regular graph.

References

Notes and References

  1. Zhang 2005.
  2. Zhang 2005, p. 290.
  3. Zhang 2005, p. 299.
  4. Hulgan 2009, p. 2.
  5. Hulgan 2009, p. 2.
  6. Chen 2008.
  7. Zhang 2005.
  8. Huang2012
  9. Papaioannou2014

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Adjacent-vertex-distinguishing-total coloring".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2025, A B Cryer, All Rights Reserved. Cookie policy.