Colouring of S-labelled planar graphs
Colouring of S-labelled planar graphs
复制标题
DOI：
10.1016/j.ejc.2020.103198
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Li-gang Jin;T. Wong;Xuding Zhu
中科院分区：
文献类型：
--
作者：
Li-gang Jin;T. Wong;Xuding Zhu
设G是一个图，S是一个整数排列集。图G的一个S标号是一个对(D，σ)，其中D是G的一个定向，σ：E(D)→S是一个映射，它给D的每个弧e分配一个置换σe∈S。(D，σ)的一个真k-染色是一个映射f：V(G)→[k]={1，2，…，k}使得对于每个弧e=(x，y)，σe(f(X))≠f(Y)。我们称G是S-k-色的，如果G的任一S-标号(D，σ)有适当的k-染色。S-k-着色概念是许多着色概念的共同推广，包括k-着色、符号k-着色、符号Zk-着色、DP-k-着色、群着色和增益图的着色。我们感兴趣的问题是关于S 4的哪个子集S，每个平面图都是S-4可染的。我们称这样的子集为S的良子集。著名的四色定理相当于说S={idd}是好的。KráL，Pangrác和Voss的一个结果等价于说S={id，(1234)，(13)(24)}和S={id，(12)(34)，(13)(24)，(14)(23)}是不好的。这些结果被Kardoš和Narboni的一个最新结果所加强，它暗示S={idd，(12)(34)}是不好的，而朱的另一个最新结果暗示S={idd，(12)}是不好的。本文证明了如果S是S 4的一个包含Id的子集，则S是好的当且仅当S={Id}。
Assume G is a graph and S is a set of permutations of integers. An S-labelling of G is a pair (D, σ), where D is an orientation of G and σ: E (D)→ S is a mapping which assigns to each arc e of D a permutation σ e∈ S. A proper k-colouring of (D, σ) is a mapping f: V (G)→[k]={1, 2,…, k} such that σ e (f (x))≠ f (y) for each arc e=(x, y). We say G is S-k-colourable if any S-labelling (D, σ) of G has a proper k-colouring. The concept of S-k-colouring is a common generalization of many colouring concepts, including k-colouring, signed k-colouring, signed Z k-colouring, DP-k-colouring, group colouring and colouring of gain graphs. We are interested in the problem as for which subset S of S 4, every planar graph is S-4-colourable. We call such a subset S a good subset. The famous Four Colour Theorem is equivalent to say that S={i d} is good. A result of Král, Pangrác and Voss is equivalent to say that S={i d,(1234),(13)(24)} and S={i d,(12)(34),(13)(24),(14)(23)} are not good. These results are strengthened by a very recent result of Kardoš and Narboni, which implies that S={i d,(12)(34)} is not good and another very recent result of Zhu which implies that S={i d,(12)} is not good. In this paper we prove if S is a subset of S 4 containing i d, then S is good if and only if S={i d}.