The case for $\operatorname{cr}(G)=0$ (planar graphs) is given by Wagner's theorem, but what about (for instance) the family of graphs with $\operatorname{cr}(G) \leq 1$?
Excluded minors of graphs with bounded crossing number
4
$\begingroup$
graph-theory
1 Answers
2
Check out this link. It claims that the family of graphs with crossing number $\leq k$ is not minor-closed for general $k$, though I don't understand the example there. One can fix the definition so that it be minor-closed by "blatantly" enforcing it, see here. Of course, once we have a minor-closed family, Robertson-Seymour theory tells us that there is a finite list of forbidden minors.
-
0Very helpful, thank you. I understand the argument given in the first link for the claim that $cr(G/e) \nleq cr(G)$ in general, which means that the families I described are not minor-closed. – 2011-09-10