DMS Combinatorics Seminar

Speaker: Sandra Kingan (Brooklyn College, CUNY)

Title: On cyclically 4-connected cubic graphs

Abstract: A non-trivial snark is a cyclically 4-connected cubic graph with edge chromatic number 4.  One of the most significant unsolved problems in this area is to obtain precisely a snark from a smaller snark, if this is even possible. Our results are a step in this direction.  We introduce the concept of cycle spread, which generalizes the edge pair distance defined by Wormald, and show that all non-planar cyclically 4-connected cubic graphs with at least 10 vertices, other than the Mobius ladders and the Petersen graph, are obtained from the 4-ladder by bridging pairs of edges with cycle spread at least (1,2). As a consequence, we also obtain a systematic way of constructing planar cyclically 4-connected cubic graphs with at least 10 vertices. This is joint work with Robert Kingan.