Questions tagged [graph-minor]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9 votes
1 answer
210 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 ...
  • 91
6 votes
0 answers
188 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 ...
's user avatar
9 votes
1 answer
454 views

Is there an algorithm that finds the forbidden minors?

The Robertson–Seymour theorem says that any minor-closed family $\mathcal G$ of graphs can be characterized by finitely many forbidden minors. Is there an algorithm that for an input $\mathcal G$ ...
  • 13.6k
12 votes
1 answer
1k views

Number of 4 cycles

Let $C_4$ be a cycle with four vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>n\sqrt n$, how many $C_4$s exist? Is there a lower bound for this?
5 votes
0 answers
84 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 ...
  • 748
4 votes
1 answer
155 views

Properties of toroidal graph

I am interested in work pertaining to graphs that have genus 1 i.e. toroidal graphs. Specifically, i am trying to find answers to the questions below. Since toroidal graphs can be recognized in $P$ , ...
  • 1,006
4 votes
1 answer
175 views

Minor and subdivision

It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$. Moreover, a graph $G$ has one of $K_{3,3}$ or $...
  • 1,006
10 votes
2 answers
335 views

Finding subgraphs with high treewidth and constant degree

I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth ...
  • 7,485
6 votes
0 answers
148 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 ...
  • 1,006
4 votes
1 answer
132 views

Hadwiger number under matching contraction

Given a graph $G$ with Hadwiger number $h(G)$ and a matching $M$ of $G$. Let $G/M$ be the simple graph obtained by contracting $M$. I am looking for a lower bound on the Hadwiger number of $G/M$ as a ...
  • 305
9 votes
2 answers
284 views

Something-Treewidth Property

Let $s$ be a graph parameter (ex. diameter, domination number, etc) A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph $G\in \mathcal{...
19 votes
1 answer
434 views

Minor closed properties that are explicitly MSO expressible

Below, MSO denotes the monadic second order logic of graphs with vertex-set and edge-set quantifications. Let $\mathcal{F}$ be a minor closed family of graphs. It follows from Robertson and Seymour'...
13 votes
1 answer
353 views

Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

Let $k$ be fixed, and let $G$ be a (connected) graph. If I'm not mistaken, it follows from the work of Bodlaender [1, Theorem 3.11] that if the treewidth of $G$ is roughly at least $2k^3$, then $G$ ...
  • 3,160
5 votes
1 answer
320 views

Sparser Bipartite graphs?

Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members. Let $\mathcal{C}$ be a ...
  • 2,267
9 votes
2 answers
272 views

Understanding graph minor theorem

This question is two-fold, and is mainly reference-oriented: Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know ...
  • 7,747
19 votes
1 answer
449 views

Algorithmic advantages of pathwidth over treewidth

Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth ...
8 votes
2 answers
203 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let $G$...
18 votes
1 answer
281 views

A good Library for testing whether a minors exists in a graph?

I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?
  • 289
13 votes
2 answers
275 views

Complexity of computing a densest minor

Consider the following problem. Input: An undirected graph $G=(V,E)$. Output: A graph $H$ which is a minor of $G$ with the highest edge density among all minors of $G$, i.e., with the highest ratio $|...
4 votes
1 answer
186 views

H-induced Containment problem

In the paper "On Graph Contractions and Induced Minors" by Pim van't Hof et al. they showed that this problem is fi xed parameter tractable in |VH| if G belongs to any non-trivial minor-closed graph ...
  • 1,006
6 votes
1 answer
329 views

Complexity of finding large grid minors

What is the complexity of finding the largest $k\times k$ grid graph that is a minor of a given graph $G$? It is FPT in $k$, and it seems likely to be NP-hard (or NP-complete in a decision version ...
8 votes
2 answers
583 views

Grid minor in digraphs

Thor Johnson, et al, in their paper: Directed Tree Width, introduced a definition for directed grid $J_k$, and they conjectured: $(5.1)$ For every integer $k$ there exists an integer $N$ such that ...
  • 3,430
11 votes
1 answer
412 views

MSO properties, planar graphs and minor-free graphs

Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. This is one of the most well-known ...
6 votes
0 answers
330 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$?...
  • 343
15 votes
1 answer
503 views

Decomposing graphs of genus one

Planar graphs are $K_{3,3}$-free. Such graphs can be decomposed into tri-connected components, which are known to be either planar or $K_5$ components. Is there such a "nice" decomposition of ...
17 votes
2 answers
1k views

Forbidden minors for bounded treewidth graphs

This question is similar to one of my previous questions. It is known that $K_{t+2}$ is a forbidden minor for graphs of treewidth at most $t$. Is there a nicely-constructed, parameterized, ...
17 votes
1 answer
2k views

Forbidden minors for bounded genus graphs

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 on a torus. The number of forbidden minors for graphs ...
12 votes
1 answer
2k views

Citation showing minors are topological minors for subcubic graphs

If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$. Wikipedia cites this result from Diestel's "Graph Theory". It's listed as Prop 1.7.4 in the ...
  • 343
3 votes
0 answers
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 ...
  • 343
31 votes
5 answers
1k views

what is easy for minor-excluded graphs?

Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded ...