All Questions
Tagged with graph-minors topological-graph-theory
3 questions
3
votes
2
answers
135
views
Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?
For a graph of genus $g$, it holds that it cannot have too many disjoint 5-cliques, as each clique requires a new handle. It feels that given a graph of genus $g$, it cannot have an unbounded number ...
- 31
4
votes
2
answers
266
views
Asymptotics of list size in Robertson-Seymour theorem
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 ...
user76479
21
votes
3
answers
2k
views
Obstructions for embedding a graph on a surface of genus g
Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings.
Is the ...
- 1,180