Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|≥7 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either • G∖v is planar for some vertex v; or • G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Apex graph
- Graph minors
- Petersen graph