题  目：Beyond Ohba’s Conjecture: A Bound on Choice Number of k-chromatic graphs

报告人：Douglas West

时   间：2013年12月13日    下午4:30--5:30

地   点：东区管理科研楼 数学科学学院1611会议室

摘   要：

Let ch(G) denote the choice number of a graph G (also called “list chromatic number” or “choosability” of G). Let n and k denote the number of vertices and chromatic number of G. Noel, Reed, and Wu proved the conjecture of Ohba that ch(G) = k when n≤2k + 1. We extend this to a general upper bound: ch(G)≤max｛k,[(n+k-1)/3]｝. Our result is sharp for n ≤ 3k using Ohba’s examples, and it improves the best-known upper bound for ch(K4,…,4). This is joint work with Jonathan Noel, Hehui Wu, and Xuding Zhu.

Douglas West教授简介：

Dauglas West教授是国际著名图论与离散数学专家，先后在斯坦福大学、普林斯顿大学、伊利诺伊大学担任助理教授、副教授等职务；1991年起担任伊利诺伊大学数学系教授。2007年起担任国际著名学术刊物《Discrete Mathematics》（《离散数学》）杂志主编。迄今为止，共发表了180多篇研究论文，其中20余篇论文发表在离散数学顶尖国际期刊上；所编著的《Introduction to Graph Theory》教科书是现代最流行的几本图论教科书之一，被世界各地大学广泛采用。West教授在极值图论、图的结构分析和表示理论、半序集理论、Ramsey理论等方面作出了杰出的贡献。

主办单位：  中国科学技术大学数学科学学院

                     中科院吴文俊数学重点实验室

欢迎广大师生参加！