Artículos de revistas
The total-chromatic number of some families of snarks
Registro en:
Discrete Mathematics. Elsevier Science Bv, v. 311, n. 12, n. 984, n. 988, 2011.
0012-365X
WOS:000290504200010
10.1016/j.disc.2011.02.013
Autor
Campos, CN
Dantas, S
de Mello, CP
Institución
Resumen
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) The total-chromatic number chi(T) (C) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. It is known that the problem of determining the total-chromatic number is NP-hard, and it remains NP-hard even for cubic bipartite graphs. Snarks are simple connected bridgeless cubic graphs that are not 3-edge-colourable. In this paper, we show that the total-chromatic number is 4 for three infinite families of snarks, namely, the Flower Snarks. the Goldberg Snarks, and the Twisted Goldberg Snarks. This result reinforces the conjecture that all snarks have total-chromatic number 4. Moreover, we give recursive procedures to construct a total-colouring that uses 4 colours in each case. (C) 2011 Elsevier B.V. All rights reserved. 311 12 984 988 Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)