| Abstrakt: | An important part of this thesis are snarks, cubic graphs with no 3-edge-colouring.
There have been several works which investigated the decompositions and reductions
of snarks. The complete understanding of k-reductions of snarks, for any given k, was
already achieved [Nedela, ©koviera, Decompositions and Reductions of Snarks, 1996].
However, the analysis of k-decompositions is only complete for k ≤ 5. This work
builds upon the exploration of 6-decompositions in work [Karabáą, Máčajová, Nedela,
6-decompositions of snarks, 2013].
K-decomposition of a snark is dividing a snark with a k-edge-cut and adding a small
number of vertices and edges to resulting components to make them snarks of a smaller
or equal order.
To better understand k-decomposition, we were studying the proper 3-edge-colourability
of cubic k-poles, which are graphs with all vertices of degree three except for k ordered
vertices of degree one. A colouring set is a set of k-tuples of colours 0, 1, and 2, called
boundary colourings. Given any proper 3-edge-colouring of a cubic k-pole, its bound-
ary colouring is the tuple of colours of its edges incident to vertices of degree one. The
colouring set of a cubic k-pole is a set of all its possible boundary colourings.
The primary objective of this thesis was to identify realisable colouring sets, defined
as those that are colouring sets of some cubic k-pole. We will refer to colouring sets that
satisfy two necessary conditions, the Parity Lemma and Kempe Closeness, as plausible.
Two equivalence relations can be unified into sk-equivalence: one under which colouring
sets with the same plausible complement are equivalent, and the second, which can be
obtained by permutating edges.
The unifying sk-equivalence divides the colouring sets into 170 classes. For the
purposes of k-decomposition, we only needed to find one colouring set from each class.
Sk-equivalence also helps us realise such colouring sets more effectively. A range of
algorithms is applied to determine the realisability of the colouring sets, from the
expansion of a colouring set of an empty graph by adding edges to combining existing
colouring sets of realised k-poles. This study successfully identifies 115 out of 170
colouring set classes. The remaining 55 classes constitute roughly 0.1% of all plausible
colouring sets, suggesting their rarity and potential non-realisability.
|
|---|