| Meno: | Matúą |
|---|---|
| Priezvisko: | Buček |
| Názov: | Morphology of small uncolourable graphs with maximum degree 4 |
| Vedúci: | doc. RNDr. Ján Mazák, PhD. |
| Rok: | 2026 |
| Kµúčové slová: | edge colouring, chromatic index, maximum degree 4, uncolourable graphs, morphology |
| Abstrakt: | This thesis initiates a morphological study of uncolourable graphs and multigraphs with maximum degree 4, in the spirit of the established theory of snarks. We generate complete lists of uncolourable 4-regular graphs up to 20 vertices, simple graphs with maximum degree 4 up to 15 vertices, and multigraphs with maximum degree 4 up to 14 vertices. We identify several trivial reasons for uncolourability and investigate the remaining graphs in detail. Among 4-regular graphs we find 15 nontrivially uncolourable graphs, each containing one of 3 critical subgraphs with maximum degree 4, which we also analyse. Among multigraphs we find many nontrivially uncolourable critical multigraphs and show that most of them reduce to the smallest critical uncolourable multigraph by using substitutions that preserve both uncolourability and criticality. |
Súbory bakalárskej práce:
| bucek.zip |
| BP_final.pdf |
Súbory prezentácie na obhajobe: