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

Simona Bonvicini, Andrea Vietri


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.


Edge-colouring, critical graph, Möbius strip

Full Text:


DOI: https://doi.org/10.26493/1855-3974.2039.efc

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications