Article in volume
Authors:
Myriam Preissmann
Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France
Title:
New results on Type 2 snarks
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 879-893
Received: 2020-03-16 , Revised: 2021-04-29 , Accepted: 2021-04-29 , Available online: 2021-06-01 , https://doi.org/10.7151/dmgt.2409
Abstract:
Snarks are cyclically 4-edge-connected cubic graphs that admit no proper
3-edge-coloring. A snark is of Type 1 if it has a proper total coloring of its
vertices and edges with four colors; it is of Type 2 if any total coloring
requires at least five colors. Following an extensive computer search, in 2003,
Cavicchioli et al. asked whether there exist Type 2 snarks of girth
at least 5. This question is still open, however, in 2015, Brinkmann et al.
described the first known family of Type 2 snarks of girth 4. In this work we
provide new families of Type 2 snarks of girth 4, all of which can be
constructed by a dot product of two Type 1 snarks. We also show that the
previously constructed Type 2 snarks of Brinkmann et al. do not have
this property.
Keywords:
dot product, total coloring, snark
References:
- K.I. Appel and W. Haken, Every planar map is four colorable, Amer. Math. Soc. 98 (1989).
https://doi.org/10.1090/conm/098 - M. Behzad, Graphs and Their Chromatic Numbers, Ph.D. Thesis (Michigan State University, 1965).
- D. Blanuša, Problem cetiriju boja, Glasnik Mat. Fiz. Astr. Ser. II (1946) 31–42, in Croatian.
- G. Brinkmann, J. Goedgebeur, J. Hägglund and K. Markström, Generation and properties of snarks, J. Combin. Theory Ser. B 103 (2013) 468–488.
https://doi.org/10.1016/j.jctb.2013.05.001 - G. Brinkmann, M. Preissmann and D. Sasaki, Snarks with total chromatic number $5$, Discrete Math. Theor. Comput. Sci. 17 (2015) 369–382.
- C.N. Campos, S. Dantas and C.P. de Mello, The total-chromatic number of some families of snarks, Discrete Math. 311 (2011) 984–988.
https://doi.org/10.1016/j.disc.2011.02.013 - A. Cavicchioli, T.E. Murgolo, B. Ruini and F. Spaggiari, Special classes of snarks, Acta Appl. Math. 76 (2003) 57–88.
https://doi.org/10.1023/A:1022864000162 - S. Dantas, C.M.H. de Figueiredo, M. Preissmann and D. Sasaki, The hunting of a snark with total chromatic number $5$, Discrete Appl. Math. 164 (2014) 470–481.
https://doi.org/10.1016/j.dam.2013.04.006 - B. Descartes, Network-colourings, Math. Gaz. 32(299) (1948) 67–69.
https://doi.org/10.2307/3610702 - D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Program. 1 (1971) 168–194.
https://doi.org/10.1007/BF01584085 - M. Gardner, Mathematical games: snarks, Boojums and other conjectures related to the four-color-map theorem, Scientific American 234 (1976) 126–130.
https://doi.org/10.1038/scientificamerican0476-126 - M.K. Goldberg, Construction of class $2$ graphs with maximum vertex degree $3$, J. Combin. Theory Ser. B 31 (1981) 282–291.
https://doi.org/10.1016/0095-8956(81)90030-7 - R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221–239.
https://doi.org/10.1080/00029890.1975.11993805 - R. Isaacs, Loupekhine's snarks: a bifamily of non-Tait-colorable graphs, Technical Report 263, Dept. of Math. Sci., The Johns Hopkins University, Maryland, U.S.A. (1976).
- T.R. Jensen and B. Toft, Graph Coloring Problems (John Wiley and Sons, 2011).
- M. Preissmann, C-minimal snarks, Annals Discrete Math. 17 (1983) 559–565.
https://doi.org/10.1016/S0304-0208(08)73434-0 - N. Robertson, D.P. Sanders, P.D. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997) 2–44.
https://doi.org/10.1006/jctb.1997.1750 - M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9 (1971) 396–402.
https://doi.org/10.1007/BF02771690 - P.D. Seymour, Disjoint paths in graphs, Discrete Math. 29 (1980) 293–309.
https://doi.org/10.1016/0012-365X(80)90158-2 - G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Aust. Math. Soc. 8 (1973) 367–387.
https://doi.org/10.1017/S0004972700042660 - P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh 10 (1880) 501–503.
https://doi.org/10.1017/S0370164600044643 - W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80–91.
https://doi.org/10.4153/CJM-1954-010-9 - V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964) 25–30.
- V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk 23 (1968) 117–134, in Russian.
https://doi.org/10.1070/RM1968v023n06ABEH001252
Close