Skip to main content
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).
M. Winter's user avatar
  • 12.8k
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 ...
Tony Huynh's user avatar
  • 31.8k
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$ ...
Tony Huynh's user avatar
  • 31.8k
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 ...
Tony Huynh's user avatar
  • 31.8k
9 votes
Accepted

Hadwiger number and minimal degree

No, icosahedron does not have $K_5$ as a minor being planar graph.
Fedor Petrov's user avatar
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,...
Tony Huynh's user avatar
  • 31.8k
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 ...
Tony Huynh's user avatar
  • 31.8k
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.
Fedor Petrov's user avatar
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)$ ...
Tony Huynh's user avatar
  • 31.8k
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 ...
Wojowu's user avatar
  • 27.7k
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. ...
Tony Huynh's user avatar
  • 31.8k
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 ...
Goldstern's user avatar
  • 14k
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 ...
Tony Huynh's user avatar
  • 31.8k
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 ...
Anonymous's user avatar
  • 166
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 ...
Tony Huynh's user avatar
  • 31.8k
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)$-...
David E Speyer's user avatar
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 "...
Thomas Kalinowski's user avatar
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 ...
Tony Huynh's user avatar
  • 31.8k
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\...
Jan Kyncl's user avatar
  • 6,046
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}$...
Jiachen Yuan's user avatar
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}}\...
Peter Heinig's user avatar
  • 6,031
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\...
Wojowu's user avatar
  • 27.7k
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--...
David Wood's user avatar
  • 1,273
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 (...
Marcin Wrochna's user avatar
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.
Bjørn Kjos-Hanssen's user avatar
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 ...
Peter Heinig's user avatar
  • 6,031
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. ...
David Eppstein's user avatar
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: $\...
Adam Przeździecki's user avatar
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}$$ ...
Thomas Kalinowski's user avatar
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.
Jon Noel's user avatar
  • 761

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