勷勤数学•专家报告

题      目：On Graph Edge Coloring

报  告  人：郝燕丽 博士  (邀请人：罗天文)

                                      佐治亚理工大学

时      间： 12月26日  10：30-11:30

地     点：数科院西楼114

报告人简介:

       郝燕丽，目前是佐治亚理工的Hale Visiting Assistant Peofessor。研究方向是结构图论与图的着色。
2023年在佐治亚州立大学获得数学博士学位，师从陈冠涛教授。博士期间及之后，工作主要围绕图的边着色、线性荫度猜想等相关问题展开，已在《Journal of Combinatorial Theory, Series B》和《Journal of Graph Theory》等期刊上发表多篇论文。目前，与博士后合作导师郁星星教授正在研究多重图的最优边着色问题，相关论文已投稿

摘      要：

      For a multigraph $G$, let $\chi'(G)$ denote the chromatic index of $G$, $\Delta(G)$ denote the maximum degree of $G$, and $\Gamma(G)=\lceil \Gamma^*(G)\rceil$, where $$\Gamma^*(G) = \max\{|E(H)|/\lfloor |V (H)|/2\rfloor: H \mbox{ is a subgraph of } G \mbox{ and } |V(H)|\ge 2\}.$$  As a generalization of Vizing’s classical coloring result on simple graphs, the Goldberg-Seymour conjecture, posed in the early 1970s, asserts that $\chi'(G)=\max\{\Delta(G), \Gamma(G)\}$ or $\chi'(G)=\max\{\Delta(G) + 1, \Gamma(G)\}$. Hochbaum, Nishizeki, and Shmoys conjectured in 1986 that a $\max\{\Delta(G) + 1, \chi'(G)\}$-edge-coloring of $G$ can be obtained in polynomial time in the size of $G$. This is the best one could hope for in polynomial time unless {\bf P} $=$ {\bf NP}. Dr. Guantao Chen, Xingxing Yu and Wenan Zang provide a combinatorial algorithm which finds, in $O(|V(G)|^{10}|E(G)|^3)$ time, a $\max\{\Delta(G) + 1, \Gamma(G)\}$-edge-coloring of $G$, thereby establishing the Hochbaum-Nishizeki-Shmoys conjecture and also the Goldberg-Seymour conjecture.

          欢迎老师、同学们参加、交流！