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-3974. - 2:19(2020), pp. 209-229. [10.26493/1855-3974.2039.efc]

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

Bonvicini, Simona
;
Vietri, Andrea
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
Edge-colouring, critical graph, Möbius strip
01 Pubblicazione su rivista::01a Articolo in rivista
A Möbius-type gluing technique for obtaining edge-critical graphs / Bonvicini, Simona; Vietri, Andrea. - In: ARS MATHEMATICA CONTEMPORANEA. - ISSN 1855-3974. - 2:19(2020), pp. 209-229. [10.26493/1855-3974.2039.efc]
File allegati a questo prodotto
File Dimensione Formato  
Bonivicini_M ̈obius-type_2020.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 390.44 kB
Formato Adobe PDF
390.44 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

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