| Abstrakt: | Snark je netriviálny bezmostový kubický graf, ktorého hrany nemožno zafarbiť tromi farbami. Tieto grafy majú veľký význam v dokazovaní alebo vyvracaní niekoľkých známych hypotéz teórie grafov. G. Brinkmann a kol. vygenerovali pomocou počítača všetky snarky až do rádu 36. Aby sme lepšie pochopili štruktúru a nezafarbiteľnosť snarkov, analyzujeme všetky ireducibilné cyklicky 5-súvislé snarky, opíšeme ich štruktúru a vysvetlíme, prečo sú nezafarbiteľné. Budeme sa pritom pozerať na 3-hranové-zafarbenie kubického grafu ako na nikde nulový 4-tok.
V našej práci predstavíme niekoľko operácií, ktoré nám umožnia konštruovať nekonečné triedy snarkov.
|
|---|