×

Snarks with total chromatic number 5. (English) Zbl 1319.05048

Summary: 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 \(\chi _{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 \(\chi _{T} = 4\) are said to be Type 1, and cubic graphs with \(\chi _{T} = 5\) are said to be Type 2.
Snarks are cyclically 4-edge-connected cubic graphs that do not allow a 3-edge-coloring. A. Cavicchioli et al. [Acta Appl. Math. 76, No. 1, 57–88 (2003; Zbl 1018.05033)] 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\geq 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.

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1018.05033
PDFBibTeX XMLCite
Full Text: Link