Snarki

Čižman, Teja (author), Škrekovski, Riste (mentor)

V delu si podrobneje ogledamo snarke, ki spadajo v teorijo grafov. Snark definiramo kot ciklično $4$-povezan kubični graf z ožino vsaj pet in kromatičnim indeksom štiri. Najbolj znan snark je gotovo Petersenov graf, ki je prav tako najmanjši snark in edini na desetih vozliščih. Število snarkov se glede na število vozlišč zelo hitro veča. S snarki si lahko pomagamo pri dokazovanju izreka štirih barv. Izrek je namreč ekvivalenten dokazu, da noben snark ni ravninski. Do leta 1975 je bilo znanih le pet snarkov, leta 1975 pa sta definirani dve neskončni družini snarkov, deljeni glede na njihov način konstrukcije. V prvo neskončno družino spadajo snarki, ki so konstruirani ali s točkovnim produktom ali z zvezdastim produktom. Pri obeh konstrukcijah je možno konstruirati snark tudi, če vhodna grafa nista snarka. Druga neskončna skupina snarkov so cvetlični snarki, ki dobijo ime po svoji obliki. Rufus Isaacs je v želji po definiranju tretje neskončne družine snarkov konstruiral tudi double-star snark.

• Language: Slovenian
• Keywords: teorija grafov, snark, barvanje povezav, kromatični indeks, izrek štirih barv, točkovni produkt, zvezdasti produkt, cvetlični snarki
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2024
• PID: 20.500.12556/RUL-162249
• UDC: 519.17
• COBISS.SI-ID: 208510979
• Publication date in RUL: 20.09.2024

ČIŽMAN, Teja, 2024, Snarki [online]. Bachelor’s thesis. [Accessed 5 April 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=162249

Secondary language

• Language: English
• Title: Snarks

Abstract

In this paper we take a closer look at snarks, a certain group of graphs that appears in graph theory. We define them as cyclically $4$-edge-connected cubic graphs of girth at least five and chromatic index four. Petersen graph is the most well-known snark, as well as the smallest and only snark on 10 vertices. The number of known snarks rises very fast with the number of vertices in a graph. Snarks can help us prove the four colour theorem as the four colour theorem is equivalent to the statement that every snark must be non-planar. Up until 1975 only five snarks were known. In the year 1975, Rufus Isaacs classified two infinite families of snarks, depending on their construction. The first infinite family includes snarks, constructed by the dot or the star product. And the second infinite family are flower snarks, which get their name after their flower-like shape. Rufus Isaacs also produced a completely separate new snark, the double-star snark.

• Keywords: graph theory, snark, edge colouring, chromatic index, four colour theorem, dot product, star product, flower snarks