2010/02/22 by Miroslav Chladný, Martin Škoviera · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #graph theory and CDMA systems #Graph Labeling and Dimension Problems #Mathematics #Factorization #Combinatorics #Iterated function #Order (exchange) #Isomorphism (crystallography) #Product (mathematics) #Discrete mathematics #Irreducible representation #Pure mathematics
paper · pdf · doi:10.37236/304
openalex publication_date 2010/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
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 \H1,…,Hn\ 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.