Originator(s): Michael Plummer, Vanderbilt University
Conjecture/Question: What is the largest cyclic edge-connectivity of a 5-connected planar graph? The answer is at least 10 and at most 13.
Definitions/Background/motivation: A graph is cyclically k-edge-connected if at least k edges must be removed to disconnect it into two components that each contain a cycle. The cyclic edge-connectivity is the maximum k such that the graph is cyclically k-edge-connected. The notion of cyclic edge-connectivity arose from attempts to prove the Four Color Theorem.
Comments/Partial results: Plummer [P] showed that 4-connected planar graphs can have arbitrarily high cyclic edge-connectivity; the double wheel Cm-2\join 2K1 is 4-connected (for m >= 6) and has cyclic edge-connectivity m. In the same paper, Plummer showed that 5-connected planar graphs have cyclic edge-connectivity at most 13 and exhibited a 5-connected planar graph with cyclic edge-connectivity 10.
References:
[P] Plummer, M. D. On the cyclic connectivity of planar graphs. Graph theory
and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972;
dedicated to the memory of J. W. T. Youngs), pp. 235--242. Lecture Notes in
Math., Vol. 303, Springer, Berlin, 1972.
Keywords: