威尼斯wns8885556(中国)最新网址

 
Minimum non-chromatic-choosable graphs

报告人:朱绪鼎 浙江师范大学教授

报告时间:20231510:00-11:00

报告地点:腾讯会议889-179-399

报告摘要:

     For a positive integer $k$, let $$f(k) = \min\{|V(G)|: \chi(G)=k < ch(G)\}.$$ It was conjectured by Ohba, and proved by Noel, Reed and Wu  that $f(k) \ge 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 $\lambda=\{k_1,\ldots, k_q\}$ is a set of positive integers. Let $k_{\lambda} = k_1+\ldots +k_q$. A $\lambda$-list assignment of a graph $G$ is a $k_{\lambda}$-list assignment $L$ of $G$ such that $\bigcup_{v \in V(G)}L(v)$ is partitioned into $C_1\cup \ldots \cup C_q$ and for each vertex $v$, $|L(v) \cap C_i|=k_i$. We say $G$ is $\lambda$-choosable if $G$ is $L$-colourable for every $\lambda$-list assignment $L$.  The concept of $\lambda$-choosability of graphs puts $k$-choosable and $k$-colourable in a same framework. Let $$f(\lambda)=\min\{|V(G)|: \chi(G)=k_{\lambda}, G \text {is not $\lambda$-choosable}\}.$$ We determined the value of $f(\lambda)$ for all $\lambda$. This lecture explains these results and some ideas in the proofs.

报告人简介:

        朱绪鼎,浙江师范大学特聘教授、博士生导师、浙江师范大学离散数学研究中心主任,2010年国家级人才计划入选者,研究专长是图论、算法和组合优化。在J. Combin. Theory Ser. B, J. Combin. Theory Ser. A, Combinatorica, SIAM. J.Discrete Math., J. Graph Theory, European J. Combin., Discrete Math., Discrete Appl. Math.等国际SCI期刊发表论文280 余篇,论文被引用3000余次(MathSciNet)。三十多次应邀在重要的国际学术会议上作大会报告。曾获得台湾科学委员会杰出研究奖,台湾数学学会学术奖,主持台湾杰出学者研究计划。现任J. Graph Theory, European J. Combin.Discrete Math.Contrib. Discrete Math.Discuss. Math., Graph TheoryBulletin of Academia Sinica等国际学术期刊编委。


网页发布时间: 2023-01-04