讲座题目：OPTIMIZATION PROBLEMS IN GRAPH EDGE COLORING

主办单位：长江大学信息与数学学院

报告专家：陈冠涛（GEORGIA STATE UNIVERSITY（美国），教授、博士生导师）

报告时间：2023年5月22 日 14：30-15：30

会议地点：8-406

专家简介：Guantao Chen, is the Regents’ Professor and the Chair of the Department of Mathematics and Statistics, Georgia State University. His research interests are mainly in graph theory and its applications. He works on graph structural problems in several areas, such as cycles and paths in graphs, graph coloring, and graph Ramsey theory. In recent years, most of his efforts have been in developing and understanding graph edge recoloring techniques and using them to solve some classic problems in the area. He has published more than 120 papers in major journals in combinatorics and graph theory and, with various of his collaborators, solve a number of long standing conjectures. He served as the Program Coordinator of the SIAM Discrete Mathematics Active Group (2014-2016) and a Managing Editor of the journal of Graphs and Combinatorics since 2011.

摘要：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.