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

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 217, p. 11-pg., 2017-01-30.

Resumo

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)

• Processo FAPESP: 12/10562-3 - Coloração total semiforte
• Beneficiário: Atilio Gomes Luiz
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 14/16987-1 - Problemas estruturais em teoria de grafos
• Beneficiário: Christiane Neme Campos
• Modalidade de apoio: Bolsas no Exterior - Pesquisa