应数学与统计学院张和平教授和高毓平老师邀请，美国佐治亚州大学数学与统计系陈冠涛教授将于2021年5月9日作线上报告。

报 告：Optimization problems in Graph Edge Coloring

时 间：2021年5月9号20:00

地 点：ZOOM: 990698957 (密码:523461)

摘 要：Graph edge coloring is a well established subject in the field of graph theory, it is one of the basic combinatorial optimization problems: color the edges of agraph Gwith as few colors as possible such that each edge receives a color andadjacent edges, that is,different edges incident to a common vertex, receive different colors. The minimum number of colors needed for such a coloring ofGis called thechromatic indexofG, writtenχ(G). By a result of Holyer, the determination of the chromatic index is anNP-hardoptimization problem. TheNP-hardness gives rise to the necessity of using heuristic algorithms. In particular, we are interested in upper bounds for the chromatic index that can be efficiently realized by a coloring algorithm. In this talk, we will start with the well-known Goldberg Seymour conjecture and its proof, then talk about the recent development of recoloring techniques and its applications to a number of classic problems in critical class 2 simple graphs.

欢迎广大师生参加！

报告人简介

陈冠涛，美国Georgia State University教授(the Regents’ Professor)，数学与统计系系主任。主要研究方向为图论及其应用，着重研究图的结构、图染色、Ramsey理论等，解决了图论领域10余个著名猜想。近年来在图染色领域取得重要突破，发展运用图的边重染色方法解决了该领域的数个经典问题。在组合与图论领域顶级期刊发表论文120余篇。任the SIAM Discrete Mathematics Active Group(2014-2016)项目主管，2011年以来任图论组合权威期刊《Graphs and Combinatorics》执行编委。

甘肃省应用数学与复杂系统重点实验室

数学与统计学院

萃英学院

2021年5月6日