Surjective homomorphism preserves planarity?

102 Views Asked by At

I was just wondering if for surjective homomorphism of G to H, where G is planar hold that H is planar as well.

This is clearly false for non-surjective ones, but for surjective?

How it is with other usual graph properties? Is there some survey?

1

There are 1 best solutions below

0
On

No, not even if you strengthen "surjective" to require that every edge in $H$ is the image of at least one edge in $G$.

For example, take $G=C_{10}$ (clearly planar) and $H=K_5$ (well known not to be); then a surjective homomorphism $f:G\to H$ would be given by $$ \begin{matrix}f(0) = 0 & f(1)=1 & f(2) = 2 & f(3)=3 & f(4)=4 \\ f(5) = 0 & f(6)=2 & f(7)=4 & f(8)=1 & f(9)=3 \end{matrix} $$

By the way, the other direction doesn't work either; there's an obvious surjective homomorphism from $K_{3,3}$ (also well known to be non-planar) to $K_2$ (clearly planar).