研究生课程教学大纲 第七章：图的着色(10学时) 1本章教学内容： (1)图的边着色(2学时)，(2)图的顶点着色(2学时)，(3)与色数有关的几类图、完美 图(2学时)，(4)着色的计数与色多项式(2学时)，(5)List着色与全着色。 2本章教学要求： 通过本章课程的学习，要求学生理解图的着色问题的实际意义，掌握边着色、点着色、全着 色及其应用。 3本章教学重点：着色理论的应用。 4本章教学难点：全着色问题。 课程思政： (I)G.D.Birkhoff为了尝试证明四色定理而定义的一种多项式一即色多项式.图的色多项 式不但可以得到图的色数，而且其系数还有一些”美妙”的组合性质.1968年，Read猜 想色多项式的系数满足下面特点，如系数序列的绝对值满足：(1)单峰性（先增大后减 小)：(2)对数凹性.这个看似简单的问题困扰组合学界近50年，终于在2012年被韩国 新秀June Huh应用代数几何的方法解决（结果发表于J.Amer.Math.Soc.25(2012), 907-927).这表明要在某个方面做出突破性的成果，基础必须要扎实. (2)图的着色问题在图论研究的一个重要方面（包括理论与应用以及在其它学科的应用）， 图的点着色与独立集有深刻的联系，边着色与边独立集（匹配）有深刻的联系（通过确定 Petersen图的边色数给出直观的说明). 第八章：Ramsey定理(4学时) 1本章教学内容： (1)独立集与覆盖(2学时)，(2)Ramsey定理及其应用(2学时)。 2本章教学要求： 通过本章课程的学习，要求学生理解Ramsey问题的理论与实际意义，掌握加莱恒等式和 Ramsey定理的应用。 3本章教学重点：Ramsey问题的典型应用。 4本章教学难点：求Ramsey数。 课程思政： (I)Ramsey理论包含一个重要的哲学理念，即：完全的无序是不可能的.鸽笼原理是这一 6研究生课程教学大纲 6 第七章：图的着色(10 学时) 1 本章教学内容： (1) 图的边着色（2 学时），(2) 图的顶点着色（2 学时），(3) 与色数有关的几类图、完美 图(2 学时），(4)着色的计数与色多项式（2 学时），(5) List 着色与全着色。 2 本章教学要求： 通过本章课程的学习，要求学生理解图的着色问题的实际意义，掌握边着色、点着色、全着 色及其应用。 3 本章教学重点：着色理论的应用。 4 本章教学难点：全着色问题。 课程思政: (1) G.D. Birkhoff 为了尝试证明四色定理而定义的一种多项式—即色多项式. 图的色多项 式不但可以得到图的色数, 而且其系数还有一些”美妙”的组合性质. 1968 年, Read 猜 想色多项式的系数满足下面特点, 如系数序列的绝对值满足: (1)单峰性(先增大后减 小); (2)对数凹性. 这个看似简单的问题困扰组合学界近 50 年, 终于在 2012 年被韩国 新秀 June Huh 应用代数几何的方法解决(结果发表于 J. Amer. Math. Soc. 25 (2012), 907-927). 这表明要在某个方面做出突破性的成果, 基础必须要扎实. (2) 图的着色问题在图论研究的一个重要方面(包括理论与应用以及在其它学科的应用). 图的点着色与独立集有深刻的联系, 边着色与边独立集(匹配)有深刻的联系(通过确定 Petersen 图的边色数给出直观的说明). 第八章：Ramsey 定理(4 学时) 1 本章教学内容： (1) 独立集与覆盖（2 学时），(2) Ramsey 定理及其应用（2 学时）。 2 本章教学要求： 通过本章课程的学习，要求学生理解 Ramsey 问题的理论与实际意义，掌握加莱恒等式和 Ramsey 定理的应用。 3 本章教学重点：Ramsey 问题的典型应用。 4 本章教学难点：求 Ramsey 数。 课程思政: (1) Ramsey 理论包含一个重要的哲学理念, 即: 完全的无序是不可能的. 鸽笼原理是这一