




















Assume $G$ is a graph. We view $G$ as a symmetric digraph, in which each edge $uv$ of $G$ is replaced by a pair of opposite arcs $e=(u,v)$ and $e^{-1}=(v,u)$. Assume $S$ is an inverse closed subset of permutations of positive integers. We say $G$ is $S$-$k$-colourable if for any mapping $σ: E(G) \to S$ with $σ(x,y) = (σ(y,x))^{-1}$, there is a mapping $f: V(G) \to [k]=\{1,2, \ldots, k\}$ such that for each arc $e=(x,y)$, $σ_e(f(x)) \ne f(y)$. The concept of $S$-$k$-colouring is a common generalization of many colouring concepts, including $k$-colouring, signed $k$-colouring defined by Máčajová, Raspaud and Škoviera, signed $k$-colouring defined by Kang and Steffen, correspondence $k$-colouring defined by Dvořák and Postle, and group colouring defined by Jaeger, Linial, Payan and Tarsi. We are interested in the problem as for which subset $S$ of $S_4$, every planar graph is $S$-colourable. Such a subset $S$ is called good. The famous four colour theorem is equivalent to say that $S=\{id\}$ is good. There are two conjectures on signed graph colouring, one is equivalent to $S=\{id, (12)(34)\}$ be good and the other is equivalent to $S=\{id, (12)\}$ be good. We say two subsets $S$ and $S'$ of $S_k$ are conjugate if there is a permutation $π\in S_k$ such that $S'= \{πσπ^{-1}: σ\in S\}$. This paper proves that if $S$ is a good subset of $S_4$ containing $id$, then $S$ is conjugate to a subset of $\{id, (12), (34), (12)(34)\}$. However, it remains an open problem if there is any good subset $S$ which contains $id$ and has cardinality $|S| \ge 2$. We also prove that $S=\{(12),(13),(23),(123),(132)\}$ is not good.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。