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