第十八期图论与组合数学读书班
Abstract
本次讨论为第 18 期。主题聚焦图染色中的关键极值问题：一部分讨论 Hadwiger 猜想相关工作，展示高平均度图包含大团子式的概率方法证明；另一部分研究全染色问题，利用 Lovász Local Lemma 和 Chernoff Bound 给出全色数的上界估计，向全染色猜想迈进。这两章展示了概率工具如何解决经典图染色问题。
Date
Apr 26, 2026 7:00 PM — 9:00 PM
Event
图论与组合数学讨论班
Location
北衡楼 1216
威海, 山东
基本信息
- 系列：图论与组合数学讨论班 第 18 期
- 时间：2026 年 4 月 26 日（周日）19:00–21:00
- 地点：北衡楼 1216
- 研讨主持：许凌霄
- 指导教师：宋慧敏
内容概要
本次讨论聚焦图染色中的关键极值问题。第一部分讨论 Hadwiger 猜想相关工作，展示高平均度图包含大团子式（clique minor）的概率方法证明；第二部分研究全染色（total coloring），利用 Lovász Local Lemma 和 Chernoff Bound 给出全色数的上界估计，向全染色猜想（Total Coloring Conjecture）迈进。这些内容展示了概率工具如何解决经典图染色问题。
海报
