| 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.
|
|---|