Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651468 | Discrete Mathematics | 2006 | 13 Pages |
A snark is a “nontrivial” cubic graph whose edges cannot be properly coloured by three colours; it is irreducible if each nontrivial edge-cut divides the snark into colourable components. Irreducible snarks can be viewed as simplest uncolourable structures. In fact, all snarks can be composed from irreducible snarks in a suitable way. In this paper we deal with the problem of the existence of irreducible snarks of given order and cyclic connectivity. We determine all integers n for which there exists an irreducible snark of order n , and construct irreducible snarks with cyclic connectivity 4 and 5 of all possible orders. Moreover, we construct cyclically 6-connected irreducible snarks of each even order ⩾210⩾210. (Cyclically 7-connected snarks are believed not to exist.)