»ã±¨Ö÷Ì⣺ƽÃæͼµÄÁбí4-Ⱦɫ£¨List 4-colouring of planar graphs£©

±¨ ¸æ ÈË£ºÖìÐ÷¶¦ ½ÌÊÚ£¨Õ㽭ʦ·¶´óѧ£©

»ã±¨¹¦·ò£º2022Äê4ÔÂ1ÈÕ£¨ÖÜÎ壩 10:30

²Î»á·½Ê½£ºÌÚѶ»áÒé

»áÒéID£º924-840-712

Ô¼ÇëÈË£º¿Â·öÓ¢

Ö÷°ì²¿ÃÅ£ºÀíѧԺÊýѧϵ

»ã±¨ÌáÒª£º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 direction of research is to consider lists with separation. A (k,s)-list assignment of G is a k-list assignment of G with ¨OL(x)¡ÉL(y)¨O ¡Ý 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 for any planar graph is (4,2)-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 were not much progress on the question itself. Recently, I have answered this quesiton in the affirmative. In this lecture, I shall sketch the proof.