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.

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
Full Text: DOI