$4$-Colouring of Generalized Signed Planar Graphs

Source abstract

Assume $G$ is a graph and $S$ is a set of permutations of positive integers. An $S$-signature of $G$ is a pair $(D, \sigma)$, where $D$ is an orientation of $G$ and $\sigma: E(D) \to S$ is a mapping which assigns to each arc $e=(u,v)$ a permutation $\sigma(e)$ in $S$. We say $G$ is $S$-$k$-colourable if for any $S$-signature $(D, \sigma)$ of $G$, there is a mapping $f: V(G) \to [k]$ such that for each arc $e=(u,v)$ of $G$, $\sigma(e)(f(u)) \ne f(v)$. The concept of $S$-$k$-colourable is a common generalization of many colouring concepts. This paper studies the problem as to which subsets $S$ of $S_4$, every planar graph is $S$-$4$-colourable. We call such a subset $S$ of $S_4$ a good subset. The Four Colour Theorem is equivalent to saying that $S=\{id\}$ is good. It was proved by Jin, Wong and Zhu (arXiv:1811.08584) that a subset $S$ containing $id$ is good if and only if $S=\{id\}$. In this paper, we prove that, up to conjugation, every good subset of $S_4$ not containing $id$ is a subset of $\{(12),(34),(12)(34)\}$.