Premium
Decompositions and reductions of snarks
Author(s) -
Nedela Roman,
Ŝkoviera Martin
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199607)22:3<253::aid-jgt6>3.0.co;2-l
Subject(s) - mathematics , irreducibility , combinatorics , simple (philosophy) , discrete mathematics , indecomposable module , cubic graph , characterization (materials science) , order (exchange) , graph , pure mathematics , voltage graph , line graph , philosophy , materials science , epistemology , finance , economics , nanotechnology
According to M. Gardner [“Mathematical Games: Snarks, Boojums, and Other Conjectures Related to the Four‐Color‐Map Theorem,” Scientific American , vol. 234 (1976), pp. 126–130], a snark is a nontrivial cubic graph whose edges cannot be properly colored by three colors. The problem of what “nontrivial” means is implicitly or explicitly present in most papers on snarks, and is the main motivation of the present paper. Our approach to the discussion is based on the following observation. If G is a snark with a k ‐edge‐cut producing components G 1 and G 2 , then either one of G 1 and G 2 is not 3‐edge‐colorable, or by adding a “small” number of vertices to either component one can obtain snarks G 1 and G 2 whose order does not exceed that of G . The two situations lead to a definition of a k ‐reduction and k ‐decomposition of G . Snarks that for m < k do not admit m ‐reductions, m ‐decompositions, or both are k ‐irreducible, k ‐indecomposable, and k ‐simple, respectively. The irreducibility, indecomposability, and simplicity provide natural measures of nontriviality of snarks closely related to cyclic connectivity. The present paper is devoted to a detailed investigation of these invariants. The results give a complete characterization of irreducible snarks and characterizations of k ‐simple snarks for k ≤ 6. A number of problems that have arisen in this research conclude the paper. © 1996 John Wiley & Sons, Inc.