**5**

votes

**1**answer

255 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 ...

**1**

vote

**1**answer

141 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 ...

**2**

votes

**1**answer

238 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 ...

**4**

votes

**1**answer

208 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 ...

**4**

votes

**2**answers

340 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 ...

**3**

votes

**1**answer

609 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 ...

**4**

votes

**0**answers

83 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 ...

**17**

votes

**0**answers

358 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 ...

**3**

votes

**3**answers

353 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}$) ...

**4**

votes

**1**answer

233 views

### Ref request: A graph G contains H as a minor iff it contains one of finitely many graphs as a topological minor

For definitions of graph minors and topological minors, see wikipedia's article on graph minors.
Theorem: For every graph H, there is a finite set of graphs, say S(H), such that G contains H as a ...