一、题目：

Minimum non-chromatic λ-choosable graphs

二、主讲人：

朱绪鼎

三、摘要：

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.

四、主讲人简介：

朱绪鼎，浙江师范大学数理信息工程学院任特聘教授，博士生导师，中科院数学与系统科学研究院图论组合与网络中心学术委员会副主任。主要研究方向为图论，演算法和组合优化，已在JCTB, SIAM DM, JGT, Combinatorica等国际期刊发表SCI论文200多篇，现任SIAM DM, JGT, EJC等国际学术期刊编委。

五、邀请人：

王光辉 数学学院教授

六、时间：

3月29日（周三）10:00-11:00

七、地点：

Zoom线上会议

八、联系人：

杨帆，联系方式：yangfan5262@163.com

九、主办：

山东大学数学学院