报告题目：graph edge coloring
报告人：郝燕丽 博士后
报告时间：2025年6月17日 15:00-16:00
报告地点：科技园阳光楼南815
邀请单位：91暗网
、离散数学及其应用省部共建教育部重点实验室
报告摘要：对于任意多重图G，令χ'(G)表示其边色数，Δ(G)表示最大度数，Γ(G)=max{⌈|E(H)|/⌊|V(H)|/2⌋⌉：H是G的子图且|V(H)|≥2}.作为Vizing简单图经典着色定理的推广，上世纪七十年代初提出的Goldberg-Seymour猜想断言：χ'(G) =max{Δ(G),Γ(G)}或χ'(G) =max{Δ(G)+1,Γ(G)}。Hochbaum、Nishizeki与hmoys于1986年进一步猜想：在多项式时间内可为G构造一个使用max{Δ(G)+1,χ'(G)}种颜色的边着色方案，这是在不突破P = NP限制下多项式时间算法的最优目标。我们提出了一种组合算法，可在O(|V(G)|^{10}|E(G)|^3)时间内求得G的max{Δ(G)+1,Γ(G)}边着色，从而同时证实了Hochbaum-Nishizeki-Shmoys猜想与Goldberg-Seymour猜想。该成果基于与陈冠涛、郁星星及臧文安的合作研究。
报告人简介：郝燕丽，现为佐治亚理工郁星星教授指导下的博士后，2023年于佐治亚州立大学获博士学位，师从陈冠涛教授。近些年来主要研究图的染色问题。
欢迎老师和同学们参加！
