AVD-total-colouring of complete equipartite graphs

作者：Luiz Atilio G^*; Campos C N; de Mello C P

来源：Discrete Applied Mathematics, 2015, 184: 189-195.

DOI：10.1016/j.dam.2014.11.006

• Total-colouring
• Adjacent-vertex-distinguishing-total-colouring
• Complete equipartite graph

An AVD-total-colouring of a simple graph G is a mapping pi : V (G) boolean OR E(G) -> C, C a set of colours, such that: (i) for each pair of adjacent or incident elements x, y is an element of V(G) boolean OR E(G), pi (x) not equal pi (y); (ii) for each pair of adjacent vertices x, y is an element of V (G), sets {pi (x)} boolean OR {pi (xv) : xv is an element of E(G), nu is an element of V (G)} and {pi(y)} boolean OR {pi (y nu):y nu is an element of E(G), nu is an element of V(G)} are distinct. The AVD-total-chromatic number, chi(a)'' (G), is the smallest number of colours for which G admits an AVD-total-colouring. In 2005, Zhang et al. conjectured that chi(a)'' (G) <= Delta(G) + 3 for any simple graph G. In this article this conjecture is verified for any complete equipartite graph. Moreover, if G is a complete equipartite graph of even order, then it is shown that chi(a)''= Delta(G) + 2.

• 出版日期2015-3-31