Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
Ah, thanks! Those examples make it clear that there's a substantial difference here. –  Nick Thomas Jan 24 '13 at 11:42

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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