BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Snarks Mynhardt, Kieka


Abstract: An edge colouring of a graph is an assignment of labels (colours) to the edges of a graph such that adjacent edges are assigned different colours. It is clear that if the maximum degree of the graph is k, and v is a vertex of degree k, then at least k colours are needed to colour the edges incident with v. A famous result by the Russian mathematician Vadim Vizing states that k+1 colours will always suffice to colour the edges of the whole graph. Graphs whose edges can be coloured with its maximum degree number of colours are called Class one graphs and the rest are called Class two graphs.

A snark is a 3-regular Class two graph that satisfies some additional requirements, depending on whose definition one follows. Certainly, they should be connected and bridgeless. Modern authors usually require that they be triangle-free, or even of girth at least 5, and cyclically 4-edge connected. They have been studied since the 1880’s, when the Scottish physicist Peter Tait proved that the Four Colour Theorem is equivalent to the statement that no snark is planar. The popular science writer Martin Gardner gave them the name “snark” in 1975. The name, taken from the elusive creature in Lewis Carroll’s poem The Hunting of the Snark, reflects the scarcity of examples in the years after Tait defined them. The smallest and earliest known example of a snark is the Petersen graph, discovered in 1898. Due to their connection with the Four Colour Theorem (Four Colour Conjecture, at the time), much attention was given to the pursuit of new examples of snarks (with the hope of finding a planar one, perhaps), but a second example was not discovered until 1946. Since then, more examples have been discovered, including infinite families.

I will discuss early examples and infinite families of snarks and their connections to well-known results and conjectures in graph theory, highlighting contributions made by women on snarks (Amanda Chetwynd, Myriam Preissmann, sarah-marie belcastro, Carla Fiori, Beatrice Ruini (all contemporary)) and other topics in graph theory (Henda Swart, 1939 – 2016, whose legacy is the top quality researchers whom she inspired, Fan Chung, Penny Haxell, to mention but a few).

About the speaker: Kieka Mynhardt was born in Cape Town and lived in South Africa until 2002, when she moved to Victoria, Canada. She obtained her PhD from the University of Johannesburg under the supervision of Izak Broere. She started her professional career at the University of Pretoria, moving to the University of South Africa, also in Pretoria, after two years. She now holds a professorship at the University of Victoria.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International