Speaker: Zhu Xuding, Distinguished professor, Doctoral supervisor, College of Mathematics and Information Engineering, Zhejiang Normal University

Date: March 29, 2023

Time: 10:00-11:00

Location: Zoom

Sponsor: School of Mathematics, Shandong University

Abstract:

For a positive integer k, let f(k)=min{|V(G)|:χ(G)=k<ch(G)}. It was conjectured by Ohba, and proved by Noel, Reed and Wu that f(k)≥2k+2. This bound is sharp if k is even. Noel conjectured that if k is odd, then f(k)=2k+3. We proved this conjecture and hence determined the value of f(k) for all k. Assumeλ={k_1,…k_q} is a set of positive integers. Let k_λ=k_1+⋯+k_q. Aλ-list assignment of a graph G is a k_λ-list assignment L of G such that the set∪_(v∈V(G) ) L(v) of colours is partitioned into C_1∪…∪C_q and for each vertex v, |L(v)∩C_i |=k_i. We say G isλ-choosable if G is L-colourable for everyλ-list assignment L. The concept ofλ-choosability of graphs puts k-choosable and k-colourable in a same framework: Ifλ={1,…1} consists of k copies of 1, thenλ-choosable is equivalent to k-colourable. Ifλ={k}, thenλ-choosable is the same as k-choosable. For other partitionsλof k sandwiched between these two extremal partitions,λ-choosability reveals a complex hierarchy of colourabilities of graphs. Letλ=min{|V(G)|:χ(G)=k_λ}, G is notλ-choosable. We determined the value of f(λ) for allλ. This talk explains these results and some ideas in the proofs.

For more information, please visit:

https://www.view.sdu.edu.cn/info/1020/176479.htm