Geodesic
New results on Type 2 snarks
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 879-893 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 
@article{DMGT_2023_43_4_a0,
     author = {Dantas, Simone and Marinho, Rodrigo and Preissmann, Myriam and Sasaki, Diana},
     title = {New results on {Type} 2 snarks},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {879--893},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a0/}
}
TY  - JOUR
AU  - Dantas, Simone
AU  - Marinho, Rodrigo
AU  - Preissmann, Myriam
AU  - Sasaki, Diana
TI  - New results on Type 2 snarks
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 879
EP  - 893
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a0/
LA  - en
ID  - DMGT_2023_43_4_a0
ER  - 
%0 Journal Article
%A Dantas, Simone
%A Marinho, Rodrigo
%A Preissmann, Myriam
%A Sasaki, Diana
%T New results on Type 2 snarks
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 879-893
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a0/
%G en
%F DMGT_2023_43_4_a0
Dantas, Simone; Marinho, Rodrigo; Preissmann, Myriam; Sasaki, Diana. New results on Type 2 snarks. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 879-893. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a0/

[1] K.I. Appel and W. Haken, Every planar map is four colorable, Amer. Math. Soc. 98 (1989). https://doi.org/10.1090/conm/098

[2] M. Behzad, Graphs and Their Chromatic Numbers, Ph.D. Thesis (Michigan State University, 1965).

[3] D. Blanuša, Problem cetiriju boja, Glasnik Mat. Fiz. Astr. Ser. II (1946) 31–42, in Croatian.

[4] 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

[5] G. Brinkmann, M. Preissmann and D. Sasaki, Snarks with total chromatic number 5, Discrete Math. Theor. Comput. Sci. 17 (2015) 369–382.

[6] 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

[7] 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

[8] 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

[9] B. Descartes, Network-colourings, Math. Gaz. 32(299) (1948) 67–69. https://doi.org/10.2307/3610702

[10] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Program. 1 (1971) 168–194. https://doi.org/10.1007/BF01584085

[11] 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

[12] 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

[13] 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

[14] 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).

[15] T.R. Jensen and B. Toft, Graph Coloring Problems (John Wiley and Sons, 2011).

[16] M. Preissmann, C-minimal snarks, Annals Discrete Math. 17 (1983) 559–565. https://doi.org/10.1016/S0304-0208(08)73434-0

[17] 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

[18] M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9 (1971) 396–402. https://doi.org/10.1007/BF02771690

[19] P.D. Seymour, Disjoint paths in graphs, Discrete Math. 29 (1980) 293–309. https://doi.org/10.1016/0012-365X(80)90158-2

[20] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Aust. Math. Soc. 8 (1973) 367–387. https://doi.org/10.1017/S0004972700042660

[21] P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh 10 (1880) 501–503. https://doi.org/10.1017/S0370164600044643

[22] 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

[23] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964) 25–30.

[24] V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk 23 (1968) 117–134, in Russian. https://doi.org/10.1070/RM1968v023n06ABEH001252