An infinite family of Type 2 snarks with small girth obtained by Kochol’s Superposition

• Rieli Araújo UFRJ
• Celina M. H. de Figueiredo UFRJ
• Diana Sasaki UERJ
• Simone Dantas UFF

DOI: https://doi.org/10.5753/etc.2025.7019

Resumo

Snarks are cubic graphs with peculiar properties, making them relevant to several problems in graph theory, such as edge and total coloring. While infinite families of Type 1 snarks are well known, Type 2 snarks remain rare and difficult to construct. In 1996, Kochol introduced a method for constructing new snarks by combining two known snarks, usually Type 1. We apply Kochol’s superposition to obtain new Type 2 snarks. As a result, we construct an infinite family of Type 2 snarks with girth 4 by Kochol’s superposition of a known Type 2 snark with the infinite family of Goldberg snarks.

Referências

Brinkmann, G., Goedgebeur, J., Hägglund, J., and Markström, K. (2013). Generation and properties of snarks. Journal of Combinatorial Theory, Series B, 103(4):468–488.

Brinkmann, G., Preissmann, M., and Sasaki, D. (2015). Snarks with total chromatic number 5. Discrete Mathematics & Theoretical Computer Science, 17(1):369–382.

Campos, C., Dantas, S., and de Mello, C. (2011). The total-chromatic number of some families of snarks. Discrete Mathematics, 311:984–988.

Goldberg, M. K. (1981). Construction of class 2 graphs with maximum vertex degree 3. Journal of Combinatorial Theory, Series B, 31(3):282–291.

Isaacs, R. (1975). Infinite families of nontrivial trivalent graphs which are not tait colorable. The American Mathematical Monthly, 82(3):221–239.

Kochol, M. (1996). Snarks without small cycles. Journal of Combinatorial Theory, Series B, 67(1):34–47.