Using a technique which is inspired by topology we construct original examples of 3- and 4-edge critical graphs. The 3-critical graphs cover all even orders starting from 26; the 4-critical graphs cover all even orders starting from 20 and all the odd orders. In particular, the 3-critical graphs are not isomorphic to the graphs provided by Goldberg for disproving the Critical Graph Conjecture. Using the same approach we also revisit the construction of some fundamental critical graphs, such as Goldberg's infinite family of 3-critical graphs, Chetwynd's 4-critical graph of order 16 and Fiol's 4-critical graph of order 18.

A Möbius-type gluing technique for obtaining edge-critical graphs / Bonvicini, Simona; Vietri, Andrea. - In: ARS MATHEMATICA CONTEMPORANEA. - ISSN 1855-3966. - 19:2(2020), pp. 209-229. [10.26493/1855-3974.2039.efc]

A Möbius-type gluing technique for obtaining edge-critical graphs

Simona Bonvicini
;
Andrea Vietri
2020

Abstract

Using a technique which is inspired by topology we construct original examples of 3- and 4-edge critical graphs. The 3-critical graphs cover all even orders starting from 26; the 4-critical graphs cover all even orders starting from 20 and all the odd orders. In particular, the 3-critical graphs are not isomorphic to the graphs provided by Goldberg for disproving the Critical Graph Conjecture. Using the same approach we also revisit the construction of some fundamental critical graphs, such as Goldberg's infinite family of 3-critical graphs, Chetwynd's 4-critical graph of order 16 and Fiol's 4-critical graph of order 18.
2020
19
2
209
229
A Möbius-type gluing technique for obtaining edge-critical graphs / Bonvicini, Simona; Vietri, Andrea. - In: ARS MATHEMATICA CONTEMPORANEA. - ISSN 1855-3966. - 19:2(2020), pp. 209-229. [10.26493/1855-3974.2039.efc]
Bonvicini, Simona; Vietri, Andrea
File in questo prodotto:
File Dimensione Formato  
critical_submitted_AMC_minor_revision.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 359.91 kB
Formato Adobe PDF
359.91 kB Adobe PDF Visualizza/Apri
admin,+AMC_2039_2020.pdf

Open access

Tipologia: Versione pubblicata dall'editore
Dimensione 390.44 kB
Formato Adobe PDF
390.44 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1224067
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact