Construction of Irreducible and Critical Snarks with High Cyclical Connectivity
by
E. Ričanyová
Bratislava
Coauthors: M. Škoviera (Bratislava)

A snark is nontrivial cubic graph whose edges cannot be properly coloured by three colours. According to Vizings's theorem (1969), each cubic graph can be regularly coloured by 3 or 4 colours. On the other hand, due to a more recent result of Robinson and Wormald (1992) three colours are sufficient for the absolute majority of them. It turns out that several difficult conjectures in graph theory are closely connected to this ``negligible" part of cubic graphs. The process of discovering snarks was very painful: until 1974 only four interesting snarks were found. Nowadays we know several infinite families of snarks, and all snarks with order less or equal to 30 have been generated. There is a natural effort to "clean up" this great number of known snarks and to understand better their structure. In fact, many snarks are out of our interest because of their ``triviality". This means that such snarks can be constructed from smaller snarks by a simple operation. However the problem is to specify what should be taken as a criterion of non-triviality. In our work we adopt a relatively strong requirement of non-triviality - the irreducibility of a snark. Roughly speaking, a snark G is irreducible if there is no possibility of replacing an induced subgraph of G by anything smaller so that the resulting graph remains cubic and uncolorable. Each irreducible snark is non-trivial also in the sense adopted by most researchers - it is cyclically 4-connected and has girth at least 5. As proved by Nedela and Skoviera, a snark is irreducible if and only if it is bicritical, that is, the removal of any two vertices leads to a colourable graph. Along with irreducibility we use also other two measures of non-triviality - the strong irreducibility and criticality of a snark. A snark is said to be strongly irreducible if the removal of any two non-adjacent edges gives rise to a colourable graph, and a snark is said to be critical if removing any two adjacent vertices produces a colourable graph. Until now, all known snarks with cyclic connectivity 6 or more have been either Isaacs snarks or constructed by the superposition, a construction method introduced by Kochol. We have been dealing with the question of which conditions must be fulfilled by snarks that form the superposition in order for the resulting graph to be irreducible or critical. We give several sufficient conditions which guarantee that the resulting snarks have one of these required properties.

Date received: May 26, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafd-21.