报告题目：Graph Edge Coloring
报告人：陈冠涛教授，Georgia State University
报告摘要：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, written χ(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.
报告人简介：陈冠涛，美国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).
报告时间：2021年2月19日（周五）10:00-11:00
报告地点：腾讯会议 ID: 770 919 830
报告邀请人：图论组合优化科研团队
