Meno:  Tomáš


Priezvisko:  Vician


Názov:  Cores of uncolourable cubic graphs


Vedúci:  RNDr. Ján Mazák, PhD.


Rok:  2018


Kľúčové slová:  nezafarbiteľný kubický graf, jadro grafu, snark, uncolourable cubic graph, core of a graphs, snark


Abstrakt:  The main frame of this work consists a program for generating uncolourable cubic graphs (snarks). To these graphs we add larger snarks from an already existing database. Since generating graphs with brute force has a large time complexity, a more effective way is needed for creating the graphs. This method is inspired by the theory about the decomposition of snarks. For the resulting graphs we compute their cores, which can be later used for the verification of conjectures from the field of graph theory. In this paper we also gain some insight into complexity properties.

