# Tagged Questions

A graph $H$ is called a minor of a graph $G$ if $H$ can be obtained from $G$ by contracting edges, deleting edges, and deleting isolated vertices.

176 views

### Is there a polynomial-time algorithm to check if a signed graph contains an odd-K5 minor?

I suspect this exists, if anyone has a reference please that would be very helpful. By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite ...
45 views

### An algorithm to compute the number of graphs of size n with a given graph as a minor

I'm looking for any results regarding computing the number of graphs of size $n$ which have a given graph $H$ as a minor. Are there any known algorithms which are more efficient than a brute force ...
159 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 ...
217 views

### Is there a version of Robertson-Seymour's graph minor theorem known to apply to signed graphs?

Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the sum of the signs of its edges. For a given signed graph, a resigning may be performed ...
78 views

### A separation property of graphs of bounded tree-width

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2) Let $T$ be a tree and $r, m$ ...
49 views

### What is the relation between Hadwiger number and Treewidth?

Is there any general relation between Hadwiger number and Treewidth of a graph? Intuitively I think Hadwiger number is greater than or equal to Treewidth, but I couldn't prove it.
74 views

### What is the relation between size of maximum clique and branchwidth?

Let $bw(G)$ be the branchwidth of graph $G$ and $\omega(G)$ be the size of maximum clique in $G$. I think the following inequality holds: $$\omega(G)\leq bw(G)$$ Intuition: Assume (in reverse of ...
285 views

### A claim from “Graph minors - a survey” by Robertson and Seymour

Can someone give me a proof sketch for this: Let $\mathscr{P}_n$ be the set of all graphs which do not contain a path on $n$ vertices as a subgraph. Define the type of a graph inductively as: the type ...
153 views

### Are there good ways of relating a minor to the full determinant?

Say $A$ is a $(n-1)\times (n-1)$ matrix and we augment it by a $n^{th}$ row and a column and get a $n \times n$ matrix $B$. Is there a nice way to relate $det(B)$ and $det(A)$ and the added row and ...
244 views

### A variant of Kruskal's theorem

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of $y$...
225 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$...
375 views

### Do graphs with large number of cycles always contain large necklace minor?

Let "$k$-necklace" denote the (multi)graph obtained from a cycle of length $k$ by duplicating every edge. Note that the number of cycles in $k$-necklace is at least $2^k.$ Question : Suppose a ...
623 views

### Big binary tree as an induced subgraph

I believe this is true: Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an induced subgraph which is a subdivision of a large binary tree or the line ...
93 views

### Upper bound on size of obstruction set for wye-delta-wye reducible graphs

A graph is $Y \Delta Y$-reducible if it can be reduced to an empty graph by the following operations: $Y \leftrightarrow\Delta$ transforms; Replacing multiple edges with single edges (parallel ...
386 views

### Planar minor graphs

The theorem of Robertson-Seymour about graph minors says that there exists no infinite family of graphs such that none of them is a minor of another one. Apparently, it came as a generalization of ...
400 views

### Minor-closed classes of graphs with large numbers of excluded minors

Robertson and Seymour tell us that any minor-closed family of graphs has a finite collection of excluded minors. Standard examples include planar graphs with two excluded minors ($K_5$ and $K_{3,3}$) ...
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 ...