Xuding Zhu (Zhejiang Normal University)
List 4-colouring of planar graphs
*************************************************************************
Abstract: It is known that there are planar graphs G and 4-list assignments L of G such that G is not L-colourable. A natural direction of research is to put restrictions on the list assignments so that for any planar graph G and any 4-list assignment L of G satisfying the restrictions, G is L-colourable. One kind of lists studied in the literature is lists with separation. A (k,s)-list assignment of G is a k-list assignment of G with ∣L(x)∩L(y)∣ ≤ s for each edge xy. A graph G is called (k,s)-choosable if G is L-colourable for any (k,s)-list assignment L of G. Mirzakhani constructed a planar graph G which is not (4,3)-choosable and Kratochvíl, Tuza and Voigt proved that every planar graph is (4,1)-choosable. A natural question (asked by Kratochvíl, Tuza and Voigt) is whether every planar graph is (4,2)-choosable. This question received a lot of attention, but there was not much progress. Recently, I proved that the answer to this question is positive. In this lecture, I shall sketch the proof.
