Critical and Bicritical Snarks of Cyclic Connectivity 4
by
M. Chladný
Bratislava
Coauthors: M. Skoviera (Bratislava)

A snark is a ``non-trivial'' cubic graph with edge chromatic number 4. It has become customary that - in this context - a non-trivial graph means a cyclically 4-edge-connected graph with girth at least 5. This is because a snark deviating from this girth-and-connectivity condition can be obtained from a smaller snark or two smaller snarks in a trivial manner.

Nevertheless, a snark can also be considered trivial in much more general situations. This can be stated in terms of reductions and decompositions as defined by Nedela and Skoviera in [``Decompositions and Reductions of Snarks'', J. Graph Theory 22 (1996), 253-279]. Roughly speaking, if a snark G contains an uncolourable induced subgraph H, such that G-V(H) is 3-edge-colourable, then G-V(H) does not contribute to the uncolourability of G, and therefore can be removed. The remaining subgraph H can be converted into a snark H' by adding at most one vertex. Thus we can say that G arises from a less trivial snark H' by adding a certain amount of unimportant vertices. If |H'| < |G|, we call the snark H' a proper reduction of G.

Reductions can be further classified into k-reductions according to how many edges are cut in the process. Therefore, when dealing with non-triviality, we are interested in k-irreducible snarks, that is, snarks that admit no proper m-reductions for all non-negative integers m < k. It is known that a snark is k-irreducible for k in {5, 6} if and only if it is critical, and for k >= 7 if and only if it is bicritical (we call a snark critical if the deletion of any two adjacent vertices produces a 3-edge-colourable graph, and bicritical if the deletion of any two distinct vertices produces a 3-edge-colourable graph). Bicritical snarks are in fact k-irreducible for all k and therefore they are of special interest as ``the most non-trivial'' of all snarks.

In our contribution we will characterize critical and bicritical snarks with cyclic connectivity 4. All such snarks can be constructed by the operation of dot-product. We will present necessary and sufficient condition for a dot-product of two snarks to be critical and a necessary condition for such a dot-product to be bicritical.

The latter will imply that the ``factors'' G₁, G₂ of a cyclically 4-connected bicritical snark G₁ . G₂ must be bicritical as well. Therefore any cyclically 4-connected bicritical snark can be decomposed into a sequence of cyclically 5-connected bicritical snarks. With this in mind, we can view cyclically 5-connected bicritical snarks as basic building blocks of all snarks.

Moreover, the difference between the conditions mentioned above allows us to construct an infinite family of strictly critical snarks, that is, snarks which are critical but not bicritical - in fact we can construct strictly critical snarks of order n for all even n >= 40.

Research partially supported by the VEGA grant 1/7152/20.

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