Questions tagged [graph-minor]

The tag has no usage guidance.

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
1answer
204 views

What is the best upper bound on the running time of the graph minor algorithm?

A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained ...
6
votes
0answers
146 views

Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications

Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ...
6
votes
0answers
138 views

Book/ Monograph on graph minor theory [Reference request]

I want to learn graph minor theory. Now i have read the very basic things and the overview from the book of R.Diestel but proceeding further is getting difficult. Currently, I am also following the ...
6
votes
0answers
322 views

Citation request: Complexity of determining if a graph exists with a minor but no subgraph in set

I'm looking for a reference of the complexity of the following problem. Let our input $C$ be a finite set of graphs. Is there a graph $G$ such that: $G$ has a minor in $C$ $G$ has no subgraph in $C$?...
5
votes
0answers
81 views

Complexity of bounded degree full contraction

This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows: Instance: A graph $G$ and two integers $d$ and $k$. Question: Is there a ...
3
votes
0answers
204 views

Name for relationship where one graph is a minor usually implies another is?

Let $G$ and $H$ be graphs with the following relationship: for some $k$, after you perform at least $k$ arbitrary subdivisions of the edges of $G$ (or the edges produced through subdivision), $H$ must ...
1
vote
0answers
44 views

Three Clique Sums of Bounded Treewidth and Bounded Genus graphs

This question asks about the forbidden minors of the class of graphs that can be formed by taking three clique sums of planar graphs and bounded treewidth graphs(The class is defined for some constant ...