Gunnar Brinkmann ; Myriam Preissmann ; Diana Sasaki - Snarks with total chromatic number 5

dmtcs:2111 - Discrete Mathematics & Theoretical Computer Science, May 29, 2015, Vol. 17 no. 1 -
Snarks with total chromatic number 5Article

Authors: Gunnar Brinkmann 1,2; Myriam Preissmann ORCID3; Diana Sasaki 4

  • 1 Department of Applied Mathematics and Computer Science [Ghent]
  • 2 Vakgroep Toegepaste Wiskunde en Informatica [Gent]
  • 3 Optimisation Combinatoire
  • 4 Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia

A k-total-coloring of G is an assignment of k colors to the edges and vertices of G, so that adjacent and incident elements have different colors. The total chromatic number of G, denoted by χT(G), is the least k for which G has a k-total-coloring. It was proved by Rosenfeld that the total chromatic number of a cubic graph is either 4 or 5. Cubic graphs with χT = 4 are said to be Type 1, and cubic graphs with χT = 5 are said to be Type 2. Snarks are cyclically 4-edge-connected cubic graphs that do not allow a 3-edge-coloring. In 2003, Cavicchioli et al. asked for a Type 2 snark with girth at least 5. As neither Type 2 cubic graphs with girth at least 5 nor Type 2 snarks are known, this is taking two steps at once, and the two requirements of being a snark and having girth at least 5 should better be treated independently. In this paper we will show that the property of being a snark can be combined with being Type 2. We will give a construction that gives Type 2 snarks for each even vertex number n≥40. We will also give the result of a computer search showing that among all Type 2 cubic graphs on up to 32 vertices, all but three contain an induced chordless cycle of length 4. These three exceptions contain triangles. The question of the existence of a Type 2 cubic graph with girth at least 5 remains open.

Volume: Vol. 17 no. 1
Section: Graph Theory
Published on: May 29, 2015
Submitted on: March 17, 2014
Keywords: edge-coloring,total-coloring,snark,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

Consultation statistics

This page has been seen 461 times.
This article's PDF has been downloaded 600 times.