HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Snarks with total chromatic number 5

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.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/hal-01196855
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, September 10, 2015 - 3:17:17 PM
Last modification on : Wednesday, November 3, 2021 - 2:56:50 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:01:38 AM

File

dmtcs-17-1-24.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Gunnar Brinkmann, Myriam Preissmann, Diana Sasaki. Snarks with total chromatic number 5. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (1), pp.369--382. ⟨10.46298/dmtcs.2111⟩. ⟨hal-01196855⟩

Share

Metrics

Record views

522

Files downloads

674