关于List Coloring Conjecture

图染色理论在离散数学中相当重要。一方面图染色经常出现在许多看起来与它无关的问题当中，例如极图理论（extremal graph theory）中；另一方面，它具有很高的应用价值（例如在time-tablingand scheduling 问题中的应用）。因经常产生一些出人意料的新结果，图染色理论往往给人以惊讶。这是一个十分迷人与流行的离散数学分支，此分支中有举世著名的四色问题。

List Coloring起始于[乌克兰]图论专家V. G. Vizing 1976年，Wolf奖得主[匈牙利]数学家P. Erdos、A. L. Rubin与H. Taylor 1979年相互独立的研究工作。包括V. G. Vizing、M. O. Albertson、Collins、Tucker、Gupta等在内的许多著名的离散数学专家独立地建议如下的猜想：

List Coloring Conjecture  对任意的有限图G，其线图L(G)的List-染色数等于L(G)的染色数。  

此猜想第一次以出版物的形式出现于离散数学家B. Bollobas（匈牙利科学院外籍院士，Fields奖得主T. Gowers的博士导师）、A. J. Harris 1985年的一篇论文。从此后它受到了高度的关注。国际数学家大会1小时（2002年）和45分钟（1990年）报告者以色列科学与人文院院士N. Alon 1993年在一综述论文中阐述了这个猜想与一些典型的图论不变量的有趣联系。丹麦图论专家T. R. Jensen 与B. Toft 1995年的书《Graph coloring problems》报告了此猜想的相关情况。N. Alon在他的多篇论文及国际数学家大会1小时报告中认为，这是一个有点令人惊奇的猜想。德国图论专家R. Diestel在其2000年的经典著作《Graph theory》、 B. Bollobas在其1998年的著作《Modern graph theory》中均对此猜想作了很好的介绍。B.Bollobas在其书中亦认为这是一令人惊奇的猜想。最近的相关情况可参看波兰青年离散数学家们的著作

《Graph colorings. Edited by Marek Kubale.Contemporary

Mathematics, 352. AMS Providence, RI, 2004》。

加拿大图论首席专家、2002年国际数学家大会45分钟报告者B. Reed在其2002的著作《Graph colouring and the probabilistic method》中对List Coloring 猜想的相关情况作了一定的介绍，认为此猜想比Total Coloring 猜想还难（后者是关于顶点染色的核心公开问题）且Total Coloring 猜想与List Coloring 猜想有深刻的联系。注意K. Ohba 猜想是关于List-染色的猜想之一，但List Coloring Conjecture是关于List-染色的最著名猜想。B. Reed与B. Sudakov的2002年国际数学家大会45分钟报告用概率方法证明了K.Ohba 猜想渐近地成立；他们最近（2005年）用概率方法沿此方向又前进了一步。

  为进攻List Coloring 猜想，概率的、代数的、组合的、拓扑的方法被发展了起来。图论专家F. Galvin 1995年用组合方法对二部图证明了此猜想成立。美国图论专家J.Kahn 1996年用概率方法证明了List Coloring 猜想渐近地成立，2000年加拿大图论专家M. Molloy & B. Reed改进了J. Kahn的结果。但这对此猜想的解决是远远不够的(B. Bollobas语)。