Search

This paper studies the choosability of signed planar graphs. We prove that every signed planar graph is 5-choosable and that there is a signed planar graph which is not 4-choosable while the unsigned graph is 4-choosable. For each k ∈ { 3 , 4 , 5 , 6 } , every signed planar graph without circuits of length k is 4-choosable. Furthermore, every signed planar graph without circuits of length 3 and of length 4 is 3-choosable. We construct a signed planar graph with girth 4 which is not 3-choosable but the unsigned graph is 3-choosable. [ABSTRACT FROM AUTHOR]

In this paper, we prove that planar graphs without cycles of length 4, 6, 9 are 3-colorable. [ABSTRACT FROM AUTHOR]

A graph G is (d 1 , d 2 , d 3) -colorable if the vertex set V (G) can be partitioned into three subsets V 1 , V 2 and V 3 such that for i ∈ { 1 , 2 , 3 } the induced graph G [ V i ] has maximum vertex-degree at most d i. So, (0 , 0 , 0) -colorability is exactly 3-colorability. The well-known Steinberg's conjecture states that every planar graph without cycles of length 4 or 5 is 3-colorable. As this conjecture being disproved by Cohen-Addad etc. in 2017, a similar question, whether every planar graph without cycles of length 4 or i is 3-colorable for a given i ∈ { 6 , ... , 9 } , is gaining more and more interest. In this paper, we consider this question for the case i = 6 from the viewpoint of improper colorings. More precisely, we prove that every planar graph without cycles of length 4 or 6 is (1,0,0)-colorable, which improves on earlier results that they are (2,0,0)-colorable and also (1,1,0)-colorable, and on the result that planar graphs without cycles of length from 4 to 6 are (1,0,0)-colorable. [ABSTRACT FROM AUTHOR]

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 }. [ABSTRACT FROM AUTHOR]