# zbMATH — the first resource for mathematics

Uniquely edge-3-colorable graphs and snarks. (English) Zbl 0966.05027
Let $$G$$ be a 3-regular simple graph that has exactly one 1-factorization. It is proved that if $$G$$ is cyclically 4-edge-connected, but not cyclically 5-edge-connected, then it contains a snark as a minor. This is an approach to the conjecture of C.-Q. Zhang [J. Graph Theory 20, No. 1, 91-99 (1995; Zbl 0854.05070)] that if $$G$$ is triangle-free, then it must have the Petersen graph as a minor. A weaker conjecture due to S. Fiorini and R. J. Wilson [Research Notes in Mathematics 16 (1977; Zbl 0421.05023); Selected topics in graph theory, 103-126 (1978; Zbl 0435.05024)] claims that if $$G$$ is planar, then $$G$$ contains a triangle. It is proved in this paper, that every counterexample to the conjecture is cyclically 5-edge-connected and that in a minimal counterexample every 5-edge-cut is trivial.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C75 Structural characterization of families of graphs
##### Keywords:
snark; uniquely edge-3-colorable
Full Text: