Snarks with total chromatic number 5
Gunnar Brinkmann, Myriam Preissmann, Diana Sasaki
Abstract
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.
Full Text: PDF