华东师范大学66周年校庆暨可信计算论坛系列报告

报告题目：四色猜想的数学证明

报告人：许进 教授

主持人：何积丰 院士

报告时间：2017年9月22日 10:00-11:30

报告地点：中北校区数学馆201

报告摘要：

设G是一个最小度≧4的4-色极大平面图，C是它的一个圈。若在G的某个Kempe等价类中，C上总着2种颜色，则称G是基于C的2-色不变圈极大平面图，由C及内部(或外部)顶点导出的子图称为G的一个基本模块。对基本模块的结构和着色展开了研究，通过引入叠展运算和基本模块运算，给出了完备的基本模块运算系统；证明了对任意2-色不变圈C，存在G中的一个4-着色f，使得f在C上的颜色数为4，进而给出了四色问题的一种数学证明。

报告人简介：

许进，理学、工学双博士。北京大学教授；中国电路与系统学会副主任委员；中国电子学会图论与系统优化专业委员会理事长；生物计算与生物信息处理专业委员会理事长；军委科技委领域专家；教育部信息安全专业教学指导委员会委员。研究方向有图论、生物计算、社交网络与信息安全等。出版专著4部、译著1部；发表论文350余篇；作为第一完成人，获国家自然科学二等奖1项、教育部自然科学一等奖2项、湖北省自然科学一等奖1项。2006年创建国际生物计算大会，先后5次担任国际生物计算机大会主席。2016年提出了一种从底层全并行的新型计算模型——探针机，理论上，只需一次探针运算，即可求解图的顶点着色、Hamilton 圈等NP-完全问题的所有解。文章《探针机》入选IEEE Computational Intelligence Society (CIS) 2016年度三篇特色论文之一，被2016年第四季度《IEEE Computational Intelligence Magazine》列为CIS出版的首篇亮点论文。近年来，对极大平面图结构与着色理论展开了深入研究，发表系列文章6篇。提出了极大平面图的扩缩运算系统，对极大平面图着色进行了系统性分类，研究了2-色不变圈极大平面图的结构与着色，并应用该成果首次以数学方式证明了四色猜想。受2017年国际组合学大会邀请作45分钟四色猜想大会报告。