I'm new to the concept of graph minors, and they feel very much like homomorphisms to me. Initially I thought to myself, "why do graph theorists call a homomorphic graph a minor?" Of course, then I learned that there's a different concept of homomorphic graphs. So my question: is there nonetheless a relationship between these concepts? Does "$H$ is a minor of $G$" imply "$G$ is homomorphic into $H$?" I'm guessing the other direction is false; if so can somebody give a counterexample? Thank you!
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Minors and homomorphisms are unrelated. Here are some examples to think about. There is a graph homomorphism from any bipartite graph to any non-discrete graph (any graph with an edge). Any cycle $C_n$ is a minor of any bigger cycle $C_m$ ($m\geq n$), but there is no homomorphism from a cycle of odd order to a cycle of even order.
In particular, $C_4$ is a minor of $C_5$, but there is no homomorphism from $C_5$ to $C_4$.
Well, you are curios about the most must difficult questions in graph theory.
There is no easy connection. But there are some connections known and establishing more connection will make big research progress.
A good nontrivial example is a slight extension of the four color theorem: If $G$ has no $K_5$ as minor then it admits a homomorphism to $K_4$.
Also see the two operations are very similar:
to get a minor you pick a pair of adjacent vertices and identify them. The you may repeat this again in the new graph and again...
to get a homomorphic image you pick a pair of non-adjacent vertices and you identify them, and may repeat...
Hope this helps