Academic Report
Title: List colouring and signed colouring of planar graphs
Reporter: ZHU Xuding(Professor) (Finalist of the "Thousand Program")
Time: April 23, 2018(Monday) AM 9:00-10:00
Location: A#1101 room, Innovation Park Building
Contact: Prof. WANG Yi(tel: 84708351-8128)
Abstract:In this lecture, we discuss relations between some conjectures concerning list colouring and signed colouring of planar graphs.
KR-Conjecture (proposed by Kündgen and Ramamurthi): If is a 4-list assignment of a planar graph G in which colours in come in pairs, say if and only if , then G is L-colourable.
Conjecture A: If is a 4-list assignment of a planar graph with, then G is L-colourable.
Conjecture B: If is a 4-list assignment of a planar graph with, then G is L-colourable.
A signed graph is a pair (G, σ), where G is a graph and assigns to each edge e a sign . For a positive integer k, let if and if . A MRS-k-colouring (respectively, a KS-k-colouring) of (G, σ) is a mapping (respectively ) such that for any, . A graph G is said to be signed MRS-k-colourable (respecitvely, KS-k-colourable) if for any signature σ of G, the signed graph (G, σ) is MRS-k-colourable (KS-k-colourable).
MRS-conjecture (proposed by Máčajová, Raspaud and Škoviera): Every planar graph is signed MRS-4-colourable.
KS-conjecture (propsoed by Kang and Steffen): Every planar graph is signed KS-4-colourable.
All these conjectures are generalizations of the well-known four colour theorems.
We prove that MRS-Conjecture implies KR-Conjecture; KS-conjecture implies Conjecture A; Conjecture A together with MR-Conjecture imply Conjecture B.
Examples are given to show that Conjectures A, B are tight, if true. We also show that MRS-Conjecture and KS-conjecture, if true, are quite tight in the sense of colouring of generalized signed graphs.
The brief introduction to the reporter: Professor of Zhejiang Normal University, director of discrete mathematics research center. In 1991, he obtained the Ph. D. in mathematics from University of Calgary, Canada.He was previously a professor at the West Bay of Zhongshan University in Taiwan, a member of the mathematics Committee of the Taiwan Science Committee, a member of the academic committee of the Taiwan Mathematics Association. He won the outstanding research award of Taiwan Science Committee, the academic award of Taiwan Mathematical Society, and hosted the Taiwan distinguished scholar research program. He was selected to the third phase of the national "Thousand Program" in 2010 and then taught at Zhejiang Normal University. His research fields are graph theory, algorithm and combinatorial optimization.
