
doi: 10.46298/dmtcs.2111
handle: 1854/LU-7052952
Graph Theory 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.
snark, total-coloring, [info.info-hc] computer science [cs]/human-computer interaction [cs.hc], [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], FAMILIES, 510, 004, Mathematics and Statistics, CUBIC GRAPHS, QA1-939, edge-coloring, [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], Mathematics, GENERATION
snark, total-coloring, [info.info-hc] computer science [cs]/human-computer interaction [cs.hc], [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], FAMILIES, 510, 004, Mathematics and Statistics, CUBIC GRAPHS, QA1-939, edge-coloring, [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], Mathematics, GENERATION
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
