AVD-total-chromatic number of some families of graphs with Delta(G)=3

Author(s)

Luiz, Atilio G. ; Campos, C. N. ; de Mello, C. P.

• Document type: Journal article
• Source: DISCRETE APPLIED MATHEMATICS; v. 217, p. 11-pg., 2017-01-30.

Abstract

An AVD-total-colouring of a simple graph G is a mapping pi : V(G) boolean OR E(G) -> {1,...,k}, k >= 1, 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); and (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), v is an element of V(G)} and {pi (y)} boolean OR {pi (yv) : yv is an element of E(G), v 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 2010, J. Hulgan conjectured that any simple graph G with maximum degree three has chi(a)'' (G) <= 5. In this article, we verify Hulgan's Conjecture for simple graphs G with Delta(G) = 3 and without adjacent vertices of maximum degree, and also for the following families of snarks: the flower snarks, generalized Blanu a snarks, and LP1-snarks. In fact, we determine the exact value of chi(a)''(G) for all families considered in this work. (C) 2016 Elsevier B.V. All rights reserved. (AU)

• FAPESP's process: 12/10562-3 - Adjacent-vertex-distinguishg-total-coloring of graphs
• Grantee: Atilio Gomes Luiz
• Support Opportunities: Scholarships in Brazil - Master
• FAPESP's process: 14/16987-1 - Selected structural problems in graph theory
• Grantee: Christiane Neme Campos
• Support Opportunities: Scholarships abroad - Research