Search Results

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 mo …

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 obstruc …

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 c …

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$ …

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 Gr …

This problem was considered by Robertson and Seymour as part of their Graph Minors Project. In fact, they present a polynomial-time algorithm for the following generalization of your problem. Let $k …

No, your inequality does not hold. You are off by a constant factor. Probably the easiest way to see this is to consider the dual notion of a tangle, which I will define now. A separation in a graph …

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 …

I have a copy of Sander's PhD thesis. Counting $K_6$, there are actually $76$ excluded minors for treewidth at most $4$ (found by computer) in the thesis, but it is unknown if this list is complete ( …

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 relie …

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)$ betw …

Here is a follow-up to Richard Stanley's comment. In his Master's thesis Hunting for torus obstructions (University of Victoria, 2002), Chambers (together with his adviser Myrvold) studied the forbid …

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

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 smalle …

I'll just remark that the fact that every surface has a finite number of excluded minors (and also topological minors) does not require the full strength of the Graph Minors Theorem. Indeed, the proo …