AVD-total-chromatic number of some families of gra... - BV FAPESP
Advanced search
Start date
Betweenand


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

Full text
Author(s):
Luiz, Atilio G. ; Campos, C. N. ; de Mello, C. P.
Total Authors: 3
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