Uniquely edge-3-colorable graphs and snarks

DOI10.1007/PL00007221MaRDI QIDQ1586579zbMATH OpenFDO

Publication date 12 August 2001

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00007221

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Review text

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 \textit{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 \textit{S. Fiorini} and \textit{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.

Recommendations

Cited in

(5)

This page was built for publication: Uniquely edge-3-colorable graphs and snarks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1586579)