# Questions tagged [graph-minor]

The tag has no usage guidance.

30 questions
Filter by
Sorted by
Tagged with
39 views

### Complexity of recognizing unit distance graphs

A Graph is Unit Distance Embeddable (UDE) if it can be embedded in the plane such that every edge has a length of 1. A minor of a UDE graph is also UDE so by the Graph Minor theorem, there must be a ...
128 views

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

Graph-Minor Theorem of Robertson and Seymour  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 ...
314 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$ ...
874 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?
79 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 ...
127 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$ , ...
120 views

338 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'...
316 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$ ...
295 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 ...
218 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 ...
321 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 ...
192 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$...
256 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?