Colouring of S-labelled planar graphs

Abstract 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 Kral, Pangrac 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 Kardos 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 } .