Graph Minors and Subdivisions

88 Views Asked by At

Let $G$ be a graph that contains $H$ as a minor. Does there exist a subdivision $H'$ of $H$ such that there is a homomorphism $φ$ of $H'$ onto the $H$ minor, in particular, such that $φ$ is surjective on the vertices of the $H$ minor?

It has become clear to me that the answer is false, in particular looking at $K_{1, 4}$. A minor of it is two copies of $K_{1, 2}$ joined by another edge, which as it has maximum degree three, cannot contain any subdivision of $K_{1, 4}$, as such a graph has a degree four vertex. See the following picture: https://en.wikipedia.org/wiki/Graph_minor#/media/File:GraphMinorExampleB.svg.

Now, the follow-up question: Is it a vertex of degree four that makes this an issue? Can we say for instance that if $G$ contains a copy of $K_4$ as a minor it must have a homomorphic copy of a subdivision of $K_4$? The answer is clear for $K_3$, as well as cycles and paths in general. It looks like it holds for $K_{1, 3}$, but I may be incorrect, which leaves $K_4$ as an interesting claim.

Note also that subjectivity is a necessary condition. Letting $H$ be any graph, there is a homomorphism from an even subdivision of $H'$ (replacing edges with paths with $2k$ edges) into any nonempty graph $G$, as $H'$ is then bipartite.

For more context, Hajós conjectured that we can replace graph minors with subdivisions of $K_k$ as necessary for having chromatic number $k$. This is true for $k \leq 4$, and I am wondering if this is the reason why.

1

There are 1 best solutions below

0
On BEST ANSWER

Every graph $G$ that contains as a minor a graph $H$ with no vertices of degree greater than $3$ also contains a subdivision of $H$.

We can take a subgraph of $G$ such that vertices are grouped in clusters in bijection with the vertices of $H$. The edges in a cluster induce a tree, there is one edge between two clusters if and only if there is one edge between the corresponding vertices in $H$. This construction follows from the graph minors definition: All the edges not present were deleted and the remaining trees were contracted.

From this, we easily construct a subdivision: A tree in a cluster is connected by at most three vertices to other clusters. We can find a subdivision of $K_{1, 3}$ that links these 3 vertices: Just take the unique path between two of these vertices, then the unique path from the remaining vertex to the path.

Combining the subdivisions from all the clusters with the edges between clusters gives a subdivision of $H$.