5
$\begingroup$

What is an example of two simple, undirected graphs $G,H$ such that

  • there are no graph homomorphisms between $G, H$, and
  • $H$ is not a minor of $G$, and $G$ is not a minor of $H$

?


Definition of minor: Let $G$ be a simple undirected graph. If $S, T$ are disjoint subsets of $V(G)$ we say that $S, T$ are connected to each other if there is $s\in S, t\in T$ such that $\{s,t\}\in E(G)$. If $G,H$ are graphs, we say $H$ is a minor of $G$ if there is a family ${\cal S}$ of pairwise disjoint connected subsets of $V(G)$ and a bijection $\varphi:V(H)\to {\cal S}$ such that whenever $\{v,w\}\in E(H)$ then $\varphi(v)$ and $\varphi(w)$ are connected to each other.

$\endgroup$
2
  • 1
    $\begingroup$ $G = K_3$ and $H = C_4$? $\endgroup$ Jun 15, 2015 at 7:44
  • $\begingroup$ That's right -- Sorry - I meant the symmetric relation (not an image of each other, not a minor of each other), will correct this $\endgroup$ Jun 15, 2015 at 8:18

0

Your Answer

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

Browse other questions tagged or ask your own question.