Welcome to MathOverflow

Question

2

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices.

Say I know $g \le genus(B_{n,n}) \le g+1$: What obstructions can $B_{n,n}$ have from becoming a genus $g$ graph?

When $g=0$, we know that the obstructions are $k_{3,3}$ and $K_{5}$. In general is the number of obstructions?

For the particular case of $K_{n,n}$ what obstructions prevent it from becoming a genus $\lceil{\frac{(n-2)^{2}}{4}}\rceil -1$ graph?

edited Jun 9 2011 at 21:48

unknown (google)

community wiki

16 revisions

The Robertson–Seymour theorem guarantees that embeddability in genus $n$ is characterized by a finite list of forbidden minors, but even for the torus, no such explicit list is known (while it is known that the list has to be awfully long, Wikipedia says $\ge16000$ graphs). It is possible that being bipartite simplifies the situation, but I kind of doubt it. – Emil Jeřábek Jun 7 2011 at 18:49

Could you please provide the wiki link? Thankyou. – unknown (google) Jun 7 2011 at 19:07

3

I think it is not true that the only obstruction to being planar is having a $K_{3,3}$ subgraph. First of all, the Kuratowski theorem is for minors, not subgraphs, and a bipartite graph could still have a $K_5$ minor. For example, take $K_5$ and subdivide each edge by adding a vertex in the middle. – Matthew Kahle Jun 7 2011 at 19:19

@Matthew Kahle: We have only bipartite graphs!! Any such obstruction reduces to $K_{3,3}$. – unknown (google) Jun 7 2011 at 19:25

1

@unknown (google): The subdivided $K_5$ I described is bipartite, non-planar, and has no $K_{3,3}$ subgraphs (or minors). – Matthew Kahle Jun 8 2011 at 1:18

show 2 more comments

Bipartite Obstructions to genus $g+1$ Bipartite graph from becoming genus $g$.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.