Ask a Question

Prefer a chat interface with context about you and your work?

Complete minors in complements of nonseparating planar graphs

Complete minors in complements of nonseparating planar graphs

We prove that the complement of any non-separating planar graph of order $2n-3$ contains a $K_n$ minor, and argue that the order $2n-3$ is lowest possible with this property. To illustrate the necessity of the non-separating hypothesis, we give an example of a planar graph of order 11 whose complement …