2013/12/06 by Iain Crump, Crump, Iain · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Advanced Topics in Algebra #Combinatorics (math.CO) #FOS: Mathematics #Mathematics and Applications #graph theory and CDMA systems #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1312.1951
arxiv created 2013/12/06 · openalex publication_date 2013/12/06 · arxiv updated 2013/12/09 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
For a set of five edges, a graph splits if one of the associated Dodgson polynomials is equal to zero. A graph G splitting for every set of five edges is a minor-closed property. As such there is a finite set of forbidden minors F such that if a graph H does not contain a minor isomorphic to any graph in F, then H splits. In this paper we prove that if a graph G is simple, 3-connected, and splits, then G must not contain any minors isomorphic to K5, K3,3, the octahedron, the cube, or a graph that is a single delta-Y transformation away from the cube. As such this is the set of all simple 3-connected forbidden minors. The complete set of 2-connected or non-simple forbidden minors remains unresolved, though a number have been found.