Optimal Total Coloring a New Infinite Family of Snarks Obtained with Kochol’s Superposition
DOI:
https://doi.org/10.5540/03.2026.012.01.0324Palabras clave:
Snarks, Kochol’s Superposition, Total ColoringResumen
Snarks are cubic graphs with peculiar properties, making it very difficult to construct new snarks. In 1996, Kochol introduced a method that allows us to obtain a new snark from two known snarks; this construction is called Kochol’s superposition. We were able to construct an infinite family of girth 4 snark through Kochol’s superposition of Flower snarks (known to be Type 1) and a girth 4 snark (known to be Type 2), which allowed us to obtain new snarks from known ones. This work shows that all members of this new family are Type 2.
Descargas
Citas
M. Behzad. “Graphs and Their Chromatic Numbers”. PhD thesis. Michigan: Michigan State University, 1965. DOI: https://doi.org/doi:10.25335/j5he-k143.
G. Brinkmann, J. Goedgebeur, J. Hägglund, and K. Markström. “Generation and properties of snarks”. In: Journal of Combinatorial Theory, Series B 103.4 (2013), pp. 468–488. DOI: https://doi.org/doi:10.1016/j.jctb.2013.05.001.
G. Brinkmann, M. Preissmann, and D. Sasaki. “Snarks with total chromatic number 5”. In: Discrete Mathematics & Theoretical Computer Science 17.1 (2015), pp. 369–382. DOI: https://doi.org/doi:10.46298/dmtcs.2111.
C. N. Campos, S. Dantas, and C. P. de Mello. “The total-chromatic number of some families of snarks”. In: Discrete Mathematics 311 (2011), pp. 984–988. DOI: https://doi.org/doi:10.1016/j.disc.2011.02.013.
L. Carroll. The Hunting of the Snark. Macmillan, 1876.
M. Gardner. “Mathematical games: Snarks, Boojums and other conjectures related to the four-color-map theorem”. In: Scientific American 234.4 (1976), pp. 126–131.
R. Isaacs. “Infinite families of nontrivial trivalent graphs which are not Tait colorable”. In: The American Mathematical Monthly 82.3 (1975), pp. 221–239. DOI: https://doi.org/doi:10.1080/00029890.1975.11993805.
R. Isaacs. “Loupekhine’s snarks: A bi-family of non-tait-colorable graphs.” In: Technical Report 263 (1976).
T. Kaiser, A. King, and D. Král. “Fractional total colourings of graphs of high girth”. In: Journal of Combinatorial Theory, Series B 101.6 (2011), pp. 383–402. DOI: https://doi.org/doi:10.1016/j.jctb.2010.12.005.
M. Kochol. “Snarks without Small Cycles”. In: Journal of Combinatorial Theory, Series B 67.1 (1996), pp. 34–47. DOI: https://doi.org/doi:10.1006/j.jctb.1996.0032.
M. Rosenfeld. “On the total coloring of certain graphs”. In: Israel Journal of Mathematics 9 (1971), pp. 396–402. DOI: https://doi.org/doi:10.1007/BF02771690.
A. Sánchez-Arroyo. “Determining the total colouring number is NP-hard”. In: Discrete Mathematics 78.3 (1989), pp. 315–319. DOI: https://doi.org/doi:10.1016/0012-365X(89)90187-8.
P. G. Tait. “Remarks on the colouring of maps”. In: Proceedings of The Royal Society 10 (1880), pp. 501–503. DOI: https://doi.org/doi:10.1017/S0370164600044229.
N. Vijayaditya. “On total chromatic number of a graph”. In: Journal of the London Mathematical Society 2.3 (1971), pp. 405–408. DOI: https://doi.org/doi:10.1112/jlms/s2-3.3.405.
V. G. Vizing. “On an estimate of the chromatic class of a p-graph”. In: Diskret Analiz (1964), pp. 25–30.
