3
$\begingroup$

A planar graph cannot have $K_5$ and $K_{3,3}$ as minors. Robertson-Seymour theorem generalizes this by stating for every genus $g$ there is a finite list of forbidden minor graphs that are obstructions that prevent the graph from being genus $g$. Is there any result on the size of the list? Is it linear in $g$?

$\endgroup$
3
$\begingroup$

No, it is not linear in the genus; it is at least exponential in $g$. See for example this answer by David Eppstein.

$\endgroup$
  • $\begingroup$ i dont see a reference for 'at least'. $\endgroup$ – user76479 Jan 14 '16 at 14:21
  • 1
    $\begingroup$ As Eppstein mentions, if you take a graph which consists of exactly $g+1$ blocks, each of which is a $K_5$ or a $K_{3,3}$, then this will be an excluded minor for embedding in a surface of genus $g$. There are obviously at least $2^{g+1}$ such graphs. $\endgroup$ – Tony Huynh Jan 14 '16 at 15:43
2
$\begingroup$

It seems that this paper by Djidjev and Reif establishes an upper bound of $\exp(O(g)!)$ for the number of minimal forbidden minors.

Djidjev, Hristo, and John Reif. "An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs." Proceedings of the twenty-third annual ACM symposium on Theory of computing. ACM, 1991.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy