强完美图定理及相关的问题.pdfVIP

维普资讯 第37卷第2期 数 学 进 展 Vo1．37，No．2 2008~~月 ADVANCESIN MATHEMATICS April，2008 强完美图定理及相关的问题 宋春伟 (北京大学数学科学学院，北京， 100871) 摘要：介绍强完美图定理 (TheStrongPerfectGraphTheorem，SPGT)的历史和获证经过，同 时简述 SPGT被克服后生发的一些新问题，以期对图理论的一般研究起到鼓励和促进作用．因具体 的证明浩大聱曲，在技术的部分仅注重框架而不涉及细节． 关键词：完美图；Berge图； SPGC；强完美图定理 MR(2000)主题分类：05C17；05C00／中图分类号：O157．5 文献标识码：A 文章编号：1000—0917(2008)02—0153—11 1961年，法国数学家 ClaudeBerge(1926—2002)提出了强完美图猜想 (TheStrongPerfect GraphConjecture，SPGC)．这一猜想不仅极其简洁优美，而且深刻揭示了图的结构与性质之间 的联系．从问世之 日起，SPGC即广受关注，成为图理论中的主要猜想，很多数学家在其上耗费 心血．40余年后，在Berge故世前夕，Seymour等四位数学家组成的团队带来好消息：SPGC 终于被完结了，从此成为 “强完美图定理”(TheStrongPerfectGraphTheorem，简称SPGT)．最 终SPGT的论文有 179页，发表在2006年第四期的AnnalsofMathematics上．以下简要述评 征服 SPGC的历程及其影响，并且介绍一些相关的问题． 1完美图的历史与早期进展 ClaudeBerge不仅是数学家，还是雕塑师和文学家，他在精神生命的每一部分都追求美感． Gian-CarloRota曾说，Berge是对现代组合数学的复兴起关键作用的两位法国人之一 [，Prefac． Berge一生写了150余篇文章和多部专著，其中影响尤其巨大的包括 [4，7，8】和 [5】(与V．Chv~tal 合编)．Berge还是超图理论的奠基人，正是他创造了 超“图 (hypergraph)”这个词汇 [211P3·83]． 任意图的色数不会小于它的团数，所以团数是色数的一个下界．那么何时两者相等呢?譬 如，取一个?’阶完全图 和任何一个n阶图日的不交并G垒 u日，则显然x(C)= (G)=?’． 但这个事实没有意义，因为从中不能得到对 G的结构 (准确说 G的导出子图C[H1的结构)的 任何合理的了解． 完“美”的要求即是使两个参数 x与 处“处”相等；是 Berge在 1961年引 入了这个带有遗传功能的概念 [1】1而 完“美图(perfectgraph)”作为一个名词正式出现则是在 f21 中．当然在 Berge之前，T．Gallai的一个结果 [24】等价于说二部图的补图是完美的，Hajnal 和 Sur~nyi也曾研究过弦图的完美性质 [29】，但都缺乏严肃的定义．完美这个概念应用广泛．例 如，它也和信息论里的Shannoncapacity有关：一个图的Shannoncapacity总是在团数和色数 之间，所以完美图的Shannoncapacity就被这两个参数中的任一个确定了．有关完美图研究的 早期历史参见 [6]_ 以下讨论的图皆为有限的无向简单图． 定义 1．1 图G称为完美图若对G的每个导出子图 日都有x(H)： (日)． 例 1．2 已知的完美图至少有96种，最显然的例子包括二部图、完全图、偶圈、树等等． 比较重要的例子包括： 收稿 日期： 2007—08—29． E-mail：csong@math．pku．edu．cn 维普资讯 154 数 学 进