Factorisation of snarks
Summary: 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.
- Classification and characterizations of snarks
- 6-decomposition of snarks
- Cubic graphs that cannot be covered with four perfect matchings
- Morphology of small snarks
- Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs
- Superposition of snarks revisited
- Critical and flow-critical snarks coincide
- From edge-coloring to strong edge-coloring
- Odd 2-factored snarks
- Irreducible snarks of given order and cyclic connectivity
- Decompositions and reductions of snarks
- Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
- Cubic graphs with colouring defect 3
- Rotationally symmetric snarks from voltage graphs
- The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
- Fractal networks: topology, dimension, and complexity
- Measures of edge-uncolorability of cubic graphs
- Strictly critical snarks with girth or cyclic connectivity equal to 6
- Extremal spectral radius of graphs with cyclic edge-connectivity
- 4-coverable snarks, perfect matching cover, and Isaacs product
This page was built for publication: Factorisation of snarks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380465)
