Decompositions And Reductions Of Snarks
Roman Nedela, Martin Škoviera · 1996
. According to M. Gardner [9], a snark is a non-trivial cubic graph whose edges cannot be properly coloured by three colours. The problem of what `nontrivial ' means is implicitly or explicitly present in most papers on snarks, and is the main motivation of the present paper. Our approach to the discussion is based on the following observation. If G is a snark with a k-edge-cut producing components G 1 and G 2 , then either one of G 1 and G 2 is not 3-edge-colourable, or by adding a `small' number of vertices to either component one can obtain snarks ~ G 1 and ~ G 2 whose order does not exceed that of G. The two situations lead to a definition of a k-reduction and k-decomposition of G. Snarks that for m ! k do not admit m-reductions, m-decompositions or both are k-irreducible, k-indecomposable and k-simple, respectively. The irreducibility, indecomposability and simplicity provide natural measures of non-triviality of snarks closely related to cyclic connectivity. The present paper...