| Meno: | Jan |
|---|---|
| Priezvisko: | Gottweis |
| Názov: | Algorithm for testing the criticality of snarks |
| Vedúci: | Mgr. Jozef Rajník, PhD. |
| Rok: | 2026 |
| Kµúčové slová: | cubic graphs, edge coloring, critical snarks |
| Abstrakt: | A snark is a 3-regular graph that is not 3-edge-colorable. A snark is critical if, after removing any pair of adjacent vertices, it becomes 3-edge-colorable. Existing algorithms test criticality naively by iteratively removing every pair of adjacent vertices and testing whether the resulting graph is 3-edge-colorable. In this thesis, we introduce a more efficient algorithm that, in many cases, reduces the number of required colorability tests. Our approach uses information obtained from one colorability test to determine the colorability of a slightly modified input graph, thereby reducing redundant computations. The key element is a transformation of a coloring using suitably chosen cycles, which enables us to efficiently identify new critical pairs of vertices without explicitly testing every pair. The proposed algorithm therefore significantly accelerates criticality testing, as for most tested critical snarks it reduced the number of colorability tests to one. The algorithm also raises interesting theoretical questions that may contribute to further research on critical snarks. |
Súbory bakalárskej práce:
| main-en.pdf |
| gottweis2.zip |
Súbory prezentácie na obhajobe: