腾讯会议 ID：407 796 758
会议密码：052621
会议链接：//meeting.tencent.com/s/kNSbxJ3CBnIp
邀请人：许宝刚教授
摘要：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 {\em graph} $G$ with as few colors as possible such that each edge receives a color and {\em 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 {\em chromatic index} of $G$, written $\chi(G)$. By a result of Holyer, the determination of the chromatic index is an {\em NP-hard} optimization problem. The {\em 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.
个人简介：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.