6
$\begingroup$

Let $X$ and $Y$ be graphs and consider the Kronecker product: $Z = X \otimes Y$. Is it true that if $X$ excludes an $M$-minor, $Z$ excludes an $M \otimes Y$ minor?

I am particularly interested in the case where $Y$ is just an edge, and $Z$ is just the bipartite double cover of $X$.

$\endgroup$

1 Answer 1

3
$\begingroup$

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. But there are no forbidden minors for diamond cubics (one way to see this is that they have treewidth $\Omega(K^2)$ whereas a graph with $K^3$ vertices in a family with a forbidden minor would necessarily have treewidth $O(K^{3/2})$). So the existence of a forbidden minor is not preserved by arbitrary Kronecker products.

As for bipartite covers: the bipartite double cover of an infinite tiling of the plane by equilateral triangles (or a large patch of it) includes subdivisions of any finite cubic graph, obtained by drawing the graph with crossings in the plane, rounding the drawing to the triangle tiling, using the double cover to handle crossings without creating intersections, and adding little triangle loops where necessary to change between the two levels of the graph. But every graph is a minor of a cubic graph. So, again, bipartite double covers do not preserve the existence of forbidden minors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.