A Note on Complex-4-Colorability of Signed Planar Graphs

  • Arnfried Kemnitz
  • Margit Voigt


A pair $(G,\sigma)$ is called a {\it signed graph} if $\sigma: E(G) \longrightarrow \{1,-1\}$ is a mapping which assigns to each edge $e$ of $G$ a sign $\sigma(e) \in \{1,-1\}$. If $(G,\sigma)$ is a signed graph, then a {\it complex-4-coloring} of $(G,\sigma)$ is a mapping $f: V(G) \longrightarrow \{1,-1,i,-i\}$ with $i=\sqrt{-1}$ such that $f(u)f(v) \not= \sigma(e)$ for every edge $e=uv$ of $G$.

We prove that there are signed planar graphs that are not complex-$4$-colorable. This result completes investigations of Jin, Wong and Zhu as well as Jiang and Zhu on $4$-colorings of generalized signed planar graphs disproving a conjecture of the latter authors.

Article Number