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

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 …

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 …

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 …

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

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 …

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 …

Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a pol …

No, it is not linear in the genus; it is at least exponential in $g$. See for example this answer by David Eppstein.

Yes. This is one of the results of the Matroid Minors Project of Geelen, Gerards and Whittle as part of their proof of Rota's Conjecture. In fact, they prove that for any finite abelian group $\Gamm …