Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Factorisation of Snarks. | Factorisation of Snarks Miroslav Chladny and Martin Skoviera Department of Computer Science Comenius University Mlynska dolina 842 48 Bratislava Slovak Republic chladny skoviera @ Submitted Aug 18 2009 Accepted Feb 12 2010 Published Feb 22 2010 Mathematics Subject Classifications 05C15 05C76 Abstract 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 5j-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. 1 Introduction In the study of various important and difficult problems in graph theory such as the Cycle Double Cover Conjecture and the 5-Flow Conjecture one encounters an interesting but Research partially supported by VEGA grant no. 1 0634 09 by APVT project no. 51-027604 and by APVV project no. 0111-07 THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 .
