<p>The disjoint union of $n$ copies of $K_5$ (or $K_{3,3}$) is a minimal forbidden minor for the graphs of genus $n-1$; the same is true for a graph in which some of these copies share a single vertex, so that the blocks of the graph are $K_5$ or $K_{3,3}$. This follows from results in J. Battle, F. Harary, Y. Kodama and J.W.T. Youngs, "Additivity of the genus of a graph", <em>Bull. Amer. Math. Soc.</em> 68 (1962) 565–568, and is already enough to show that there are at least exponentially many forbidden minors.</p>

<p>Bojan Mohar, "An obstruction to embedding graphs in surfaces", <em>Discrete Math.</em> 78 (1989) 135–142, lists the graph formed from $K_8$ by removing a 4-cycle as having genus 2. Since $K_7$ is toroidal, this means that either $K_8\setminus C_4$ or one of its spanning subgraphs is an obstruction to torus embedding, and that graphs that have $n$ copies of this graph as their blocks have genus $2n$.</p>

<p>Mohar also shows that the graph formed from a $(2k+2)$-cycle by connecting vertex 0 to all the even vertices and vertex 1 to all the odd vertices has "relative genus" at least $\lceil k/2\rceil$. The graph is planar, but I think relative genus means that the cycle has to be a face; or you could add another vertex to the graph, connected to all of the cycle vertices, to effectively force it to be a face. Maybe this is closer to the sort of thing you want. But I don't think he shows that these graphs are minimal forbidden minors.</p>

CC BY-SA 3.0
2011-11-09T20:08:05.450Z
Your last paragraph about $(2k+2)$ cycle is what I am looking for. Thanks. I am accepting your answer.
Shiva Kintali
CC BY-SA 3.0
2011-11-09T06:42:30.753Z
2011-11-09T22:05:03.713Z
2011-11-09T22:05:03.713Z
David Eppstein
<p>It is well known that $K_5$ and $K_{3,3}$ are forbidden minors for planar graphs. There are hundreds of forbidden minors for <a href="http://en.wikipedia.org/wiki/Graph_embedding" rel="noreferrer">graphs embeddable</a> on a torus. The number of forbidden <a href="http://en.wikipedia.org/wiki/Minor_%28graph_theory%29" rel="noreferrer">minors</a> for graphs embeddable on surface of <a href="http://en.wikipedia.org/wiki/Genus_%28mathematics%29" rel="noreferrer">genus</a> <em>g</em> is an exponential function of <em>g</em>. My question is as follows :</p>

<blockquote>
  <p>Is there an explicit graph $G_t$ on <em>t</em> vertices (which is not a complete graph) such that $G_t$ is a forbidden minor for graphs embeddable on surface of genus <em>g</em>, where <em>t</em> is a function of <em>g</em> ?</p>
</blockquote>

<p>EDIT : I realized that the following theorem is known :</p>

<blockquote>
  <p>For every surface Σ there exists an integer <em>r</em> such that $K_{3,r}$ does not embed in Σ.</p>
</blockquote>

<p>So, I am looking for $G_t$ that is not complete graph, not a complete bipartite graph.</p>

CC BY-SA 3.0
2011-11-09T03:18:57.327Z
So, you want a nicely-constructed, parameterized, infinite family of graphs (other than complete graphs) that are forbidden minors for surfaces of every genus?
Derrick Stolee
CC BY-SA 3.0
2011-11-09T03:20:23.377Z
@Derrick. Yes. Precisely.
Shiva Kintali
CC BY-SA 3.0
2011-11-09T05:53:38.897Z
Then I would rephrase the question using those terms: "Is there a (simple to construct) family of graphs $\{ H_g : g \geq 1\}$ so that $H_g \not\cong K_n$ is a minimal forbidden minor for graphs embeddable on a genus $g$ surface?"
Derrick Stolee
CC BY-SA 3.0
2011-11-09T08:16:22.773Z
The "$K_5$ and $K_{3,3}$ are not minors of $G$" constraint can't be what you want. If they are not minors of $G$, then $G$ is planar, and can't be a forbidden minor for any higher genus.
David Eppstein
CC BY-SA 3.0
2011-11-09T10:47:04.637Z
@DavidEppstein I removed my modifications. Essentially, I am looking for obstructions that are "different" from $K_5$ and $K_{33}$.
Shiva Kintali
<graph-theory><co.combinatorics><graph-minor><algebraic-topology>
Forbidden minors for bounded genus graphs
Shiva Kintali
# Forbidden minors for bounded genus graphs

(Asked by: username_0 on 2011-11-09)

It is well known that $K\_5$ and $K\_{3,3}$ are forbidden minors for planar graphs. There are hundreds of forbidden minors for [graphs embeddable](http://en.wikipedia.org/wiki/Graph_embedding) on a torus. The number of forbidden [minors](http://en.wikipedia.org/wiki/Minor_%28graph_theory%29) for graphs embeddable on surface of [genus](http://en.wikipedia.org/wiki/Genus_%28mathematics%29) *g* is an exponential function of *g*. My question is as follows :

> Is there an explicit graph $G\_t$ on *t* vertices (which is not a complete graph) such that $G\_t$ is a forbidden minor for graphs embeddable on surface of genus *g*, where *t* is a function of *g* ?

EDIT : I realized that the following theorem is known :

> For every surface Σ there exists an integer *r* such that $K\_{3,r}$ does not embed in Σ.

So, I am looking for $G\_t$ that is not complete graph, not a complete bipartite graph.

**Tags:** graph-theory, co.combinatorics, graph-minor, algebraic-topology

> **Comments:**
> **username_1**: So, you want a nicely-constructed, parameterized, infinite family of graphs (other than complete graphs) that are forbidden minors for surfaces of every genus?  
> **username_0**: @Derrick. Yes. Precisely.  
> **username_1**: Then I would rephrase the question using those terms: "Is there a (simple to construct) family of graphs $\{ H_g : g \geq 1\}$ so that $H_g \not\cong K_n$ is a minimal forbidden minor for graphs embeddable on a genus $g$ surface?"  
> **username_2**: The "$K_5$ and $K_{3,3}$ are not minors of $G$" constraint can't be what you want. If they are not minors of $G$, then $G$ is planar, and can't be a forbidden minor for any higher genus.  
> **username_0**: @DavidEppstein I removed my modifications. Essentially, I am looking for obstructions that are "different" from $K_5$ and $K_{33}$.  

---

## 1 answers

### Answer by username_2 on 2011-11-09. Score: 16 | Accepted answer

The disjoint union of $n$ copies of $K\_5$ (or $K\_{3,3}$) is a minimal forbidden minor for the graphs of genus $n-1$; the same is true for a graph in which some of these copies share a single vertex, so that the blocks of the graph are $K\_5$ or $K\_{3,3}$. This follows from results in J. Battle, F. Harary, Y. Kodama and J.W.T. Youngs, "Additivity of the genus of a graph", *Bull. Amer. Math. Soc.* 68 (1962) 565–568, and is already enough to show that there are at least exponentially many forbidden minors.

Bojan Mohar, "An obstruction to embedding graphs in surfaces", *Discrete Math.* 78 (1989) 135–142, lists the graph formed from $K\_8$ by removing a 4-cycle as having genus 2. Since $K\_7$ is toroidal, this means that either $K\_8\setminus C\_4$ or one of its spanning subgraphs is an obstruction to torus embedding, and that graphs that have $n$ copies of this graph as their blocks have genus $2n$.

Mohar also shows that the graph formed from a $(2k+2)$-cycle by connecting vertex 0 to all the even vertices and vertex 1 to all the odd vertices has "relative genus" at least $\lceil k/2\rceil$. The graph is planar, but I think relative genus means that the cycle has to be a face; or you could add another vertex to the graph, connected to all of the cycle vertices, to effectively force it to be a face. Maybe this is closer to the sort of thing you want. But I don't think he shows that these graphs are minimal forbidden minors.

> **Comments:**
> **username_0**: Your last paragraph about $(2k+2)$ cycle is what I am looking for. Thanks. I am accepting your answer.  

---

