1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

New Results on Type 2 Snarks1

Published Online: 17 Jun 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 16 Mar 2020
Accepted: 29 Apr 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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, Cavicchioli et al. (2003) 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

MSC 2010

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

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

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

[4] G. Brinkmann, J. Goedgebeur, J. H¨agglund and K. Markström, Generation and properties of snarks, J. Combin. Theory Ser. B 103 (2013) 468–488. doi: https://doi.org/10.1016/j.jctb.2013.05.00110.1016/j.jctb.2013.05.001Search in Google Scholar

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

[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. doi: https://doi.org/10.1016/j.disc.2011.02.01310.1016/j.disc.2011.02.013Search in Google Scholar

[7] A. Cavicchioli, T.E. Murgolo, B. Ruini and F. Spaggiari, Special classes of snarks, Acta Appl. Math. 76 (2003) 57–88. doi: https://doi.org/10.1023/A:102286400016210.1023/A:1022864000162Search in Google Scholar

[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. doi: https://doi.org/10.1016/j.dam.2013.04.00610.1016/j.dam.2013.04.006Search in Google Scholar

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

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

[11] M. Gardner, Mathematical games: snarks, Boojums and other conjectures related to the four-color-map theorem, Scientific American 234 (1976) 126–130. doi: https://doi.org/10.1038/scientificamerican0476-12610.1038/scientificamerican0476-126Search in Google Scholar

[12] M.K. Goldberg, Construction of class 2 graphs with maximum vertex degree 3, J. Combin. Theory Ser. B 31 (1981) 282–291. doi: https://doi.org/10.1016/0095-8956(81)90030-710.1016/0095-8956(81)90030-7Search in Google Scholar

[13] R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221–239. doi: https://doi.org/10.1080/00029890.1975.1199380510.1080/00029890.1975.11993805Search in Google Scholar

[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).Search in Google Scholar

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

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

[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. doi: https://doi.org/10.1006/jctb.1997.175010.1006/jctb.1997.1750Search in Google Scholar

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

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

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

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

[22] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80–91. doi: https://doi.org/10.4153/CJM-1954-010-910.4153/CJM-1954-010-9Search in Google Scholar

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo