报告名称：Optimization problems in Graph Edge Coloring

主办单位：数学与统计学学院

报告专家：陈冠涛

专家所在单位：Georgia State University

报告时间：2021年5月6日9：00

报告地点：腾讯会议（会议ID：423 372 988）

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

报告摘要：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 a graph G with as few colors as possible such that each edge receives a color and adjacent edges, that is, different edges incident to a common vertex, receive different colors. The minimum number of colors needed for such a coloring of G is called the chromatic index of G. By a result of Holyer, the determination of the chromatic index is an NP-hard optimization problem. The NP-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.

邀请人：刘慧清

（审核：郑大彬）