Factorisation of snarks

Miroslav Chladný ; Martin Škoviera

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

We develop a theory of factorisation of snarks — cubic graphs with edge-chromatic number $4$ — based on the classical concept of the dot product. Our main concern are irreducible snarks, those where the removal of every nontrivial edge-cut yields a $3$-edge-colourable graph. We show that if an irreducible snark can be expressed as a dot product of two smaller snarks, then both of them are irreducible. This result constitutes the first step towards the proof of the following "unique-factorisation" theorem: Every irreducible snark $G$ can be factorised into a collection $\{H_1,\dots,H_n\}$ of cyclically $5$-connected irreducible snarks such that $G$ can be reconstructed from them by iterated dot products. Moreover, such a collection is unique up to isomorphism and ordering of the factors regardless of the way in which the decomposition was performed. The result is best possible in the sense that it fails for snarks that are close to being irreducible but themselves are not irreducible. Besides this theorem, a number of other results are proved. For example, the unique-factorisation theorem is extended to the case of factorisation with respect to a preassigned subgraph $K$ which is required to stay intact during the whole factorisation process. We show that if $K$ has order at least $3$, then the theorem holds, but is false when $K$ has order $2$.

Détail

DOI : 10.37236/304

Classification : 05C15, 05C76