Adjacent-vertex-distinguishing-total Coloring

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'') = ∪ . 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. 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.)
:''χ''_''at''(''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 ''χ''_''at''(''G'') ≤ 2Δ(''G'')
for any simple graph ''G'' with maximum degree Δ(''G'') > 2.
In 2014, Papaioannou and RaftopoulouPapaioannou2014 described an algorithmic procedure that gives a
7-AVD-total-colouring for any 4-regular graph.

Notes

References

*
*
*
*
*
*
*
*
*
*
*
* {{cite journal , last1 = Luiz , first1 = Atílio G. , last2 = Campos , first2 = C.N. , last3 = de Mello , first3 = C.P. , year = 2015 , title = AVD-total-colouring of complete equipartite graphs , journal = Discrete Applied Mathematics , volume = 184, pages = 189, doi = 10.1016/j.dam.2014.11.006, doi-access = free

Graph coloring