23
votes

Accepted

### Does minimal degree $n$ imply a $K_n$ minor

No.
The edge-graph of the icosahedron is regular of degree five, but does not have a $K_5$ minor because it is planar (Kuratowski's theorem).

22
votes

### Does minimal degree $n$ imply a $K_n$ minor

More generally, it is a classic result (independently due to Kostochka and Thomason) that minimum degree $(\alpha+o(1))n \sqrt{\log n}$ suffices to force a $K_n$ minor, where $\alpha$ is an explicit ...

11
votes

Accepted

### Does every $4$-connected nonplanar graph contain a $K_5$-minor?

Yes, this is true and follows from Wagner's theorem. Wagner's theorem asserts that every graph with no $K_5$ minor can be built from $0$-, $1$-, $2$-, and $3$-sums from planar graphs and a fixed $8$ ...

10
votes

Accepted

### Menger's theorem with restrictions on where the paths can begin and end

There is no known necessary and sufficient condition like in Menger's theorem.
However, there is a polynomial-time algorithm that decides if the paths exist. This is one of the main results of the ...

9
votes

Accepted

### Hadwiger number and minimal degree

No, icosahedron does not have $K_5$ as a minor being planar graph.

8
votes

Accepted

### Disjoint paths between four vertices

The property that you are describing is called $2$-linked. More generally, we say that a graph is $k$-linked if it has at least $2k$ vertices and for all distinct vertices $s_1, \dots s_k, t_1, \dots,...

7
votes

### Hadwiger number and minimal degree

This is false by classic results of Kostochka and Thomason. Indeed, the claim is false even if you replace 'minimum degree $t$' with '$t$-connected'. That is, if you define $\nu(t)$ to be the ...

7
votes

Accepted

### Bounding the size of clique minor of the union of two graphs

Take a complete graph $G_n$, replace each edge $uv$ to a path $uxv$. Imagine that $ux\in A$, $vx\in B$, and that's for every edge. It looks that both $A,B$ are forests, so have small Hadwiger number.

6
votes

Accepted

### Effect of removing an edge on Hadwiger number

No, there is no such graph. Suppose $\eta(G)=n$. Let $T_1, \dots, T_n$ be a collection of vertex disjoint trees in $G$ such that for all distinct $i,j \in [n]$, there is an edge $e(ij) \in E(G)$ ...

6
votes

Accepted

### Is every finite graph an induced minor of $\omega^2$?

Definitely not all graphs are minors of $\omega^2$ - $\omega^2$ is obviously a planar graph, and hence so is each of its minors. In fact, it turns out the converse also holds - every planar graph is ...

6
votes

Accepted

### Does anyone know a specific polynomial-time algorithm to detect if a given signed graph contains an odd-K4 as a signed minor?

Yes, in my PhD thesis, we prove the stronger result that for any fixed signed graph $(G, \Sigma)$, there is a polynomial-time algorithm to test if an input signed graph contains a $(G, \Sigma)$-minor. ...

6
votes

Accepted

### Large complete minors of $\mathbb{Z}^\omega$

If I understand the definition correctly, the answer is no.
If $K_\lambda$ is a minor of $G$, then there is a 1-1 map from $K_\lambda$
into the family of (nonempty) connected subsets of $G$, such ...

6
votes

Accepted

### Does the purported proof of Rota's conjecture provide an algorithm for calculating the forbidden minors of matroids over arbitrary finite fields?

As far as I understand, the purported proof does not give an algorithm that given a finite field $\mathbb{F}$, computes the excluded minors for $\mathbb{F}$-representability. This is because it ...

5
votes

Accepted

### Directed graph minor theorems

So directed graphs are not well-quasi-ordered by butterfly minors; see the intro of [BPP]. Furthermore, there are reasons to think that many of the FPT results for graph minors may not hold in the ...

5
votes

### Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?

Yes, this is true. See my paper Subgraph densities in a surface with Gwenaël Joret and David Wood. We prove that for every $s \geq 5$, the number of $s$-cliques in a graph of Euler genus $g$ is at ...

5
votes

Accepted

### 4-color theorem for hypergraphs

This follows from the case of graphs (i.e. hypergraphs where all sets have size $\leq 2$). As I explained in the comments above, Hadwiger's conjecture says that a graph with no $K_k$ minor is $(k-1)$-...

4
votes

Accepted

### Characterizing SP-DAGs by Forbidden Minors?

You might want to have a look at the paper
Jacobo Valdes, Robert E. Tarjan, Eugene L. Lawler; The recognition of Series Parallel digraphs; STOC 1979; doi:10.1145/800135.804393
Section 4 is called "...

4
votes

Accepted

### Size of forbidden minors for treewidth

Yes, an upperbound was proved in Upper Bounds on the Size of Obstructions and Intertwines by Lagergren. In case you cannot access the paper, the relevant theorem is Theorem 5.9.
If $G$ is an ...

4
votes

### Is the "surface-minor" ordering of plane graphs a well-quasi-ordering?

This is a partial answer, for the case when the given sequence $G_1,G_2,\dots$ of plane graphs has unbounded treewidth. In such a case, for every $n$ there is an $i$ such that $G_i$ contains the $n\...

4
votes

Accepted

### Minors of graphs with infinite chromatic number

For every such $G$ there is an $M$ satisfies your requirement.
It is enough to show that for every graph $G$ with infinite chromatic number has two minors $G_{0}$ and $G_{1}$ such that
$(i)$ $G_{0}$...

4
votes

Accepted

### Complete minors and minimal degree

Not an answer but an observation: for any fixed order $r$ of the complete minor, your question can be answered by a finite search over the set of all graphs of order at most $c_{\mathrm{Kostochka}}\...

4
votes

Accepted

### Induced minors of $\{0,1\}^\omega$

Let $G=(\omega,E)$ be an arbitrary graph. Let $S_n=\{x_n\}\cup\{y_{nm}:\{n,m\}\in E\}$, where $x_n$ is the characteristic function of $\{2n\}$ and $y_{nm}$ is the characteristic function of $\{2m,2n+1\...

4
votes

Accepted

### Are K_t-minor free graphs on small vertex sets understood?

There is no known straightforward answer, but pseudorandom graphs must come into the answer. See the paper by Myers and Thomason.
[In response to the comment below] Look at recent papers by Postle--...

4
votes

Accepted

### $|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number

This weakening is still an open question, even in the very special case of graphs with $\alpha(G)=2$ (complements of triangle-free graphs). In other words, do all graphs with independence number two (...

3
votes

Accepted

### Identifying two non-adjacent vertices and the effect on the Hadwiger number

Identify two opposite vertices of the cycle graph $C_4$. This reduces the Hadwiger number from 3 to 2.

3
votes

### Does anyone know a specific polynomial-time algorithm to detect if a given signed graph contains an odd-K4 as a signed minor?

As a consequence of
[Seymour, P.D., The matroids with the max-flow min-cut property, JCT B, 23 (1977), p. 189-222],
a finite signed graph has an odd $K^4$ as signed minor
if and only if
the ...

3
votes

Accepted

### Graph minors, and Kronecker product

The diamond cubic is a subgraph of the Kronecker product of three infinite paths, and $K\times K\times K$ patches of the diamond cubic are subgraphs of the Kronecker product of three length-$K$ paths. ...

3
votes

Accepted

### Complete minors of the grid graphs $\mathbb{Z}^n$

Either I am missing something or for $n>2$ you have $m(n)=\infty$. It is enough to show this for $n=3$. Choose any $m$ and a set of edges in $E_3$ which is the union of the following three sets:
$\...

3
votes

Accepted

### Is this totally unimodular family?

I don't see that your example matrix $M$ is TU. Taking the first three columns of rows 1, 4 and 7 gives the submatrix
$$\begin{pmatrix}1&1&0\\ 1&0&1\\ 0&1&1\end{pmatrix}$$
...

3
votes

Accepted

### Complete minors in graphs of bounded diameter

No, because there exists trees with small diameter.
For example, the star on $N$ vertices has diameter $2$ and does not even contain a $K_3$ minor.

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

graph-minors × 86graph-theory × 79

co.combinatorics × 40

graph-colorings × 11

reference-request × 9

hadwiger-conjecture × 8

infinite-combinatorics × 6

set-theory × 4

algorithms × 4

trees × 4

hypergraph × 3

extremal-graph-theory × 3

topological-graph-theory × 3

planar-graphs × 3

linear-algebra × 2

matrices × 2

computational-complexity × 2

order-theory × 2

combinatorial-optimization × 2

matroid-theory × 2

directed-graphs × 2

knot-link × 2

at.algebraic-topology × 1

rt.representation-theory × 1

lo.logic × 1