设为首页 | 点击旧版 | 加入收藏
当前位置: 学院首页 -> 正文

学术信息

    学术信息

    OPTIMIZATION PROBLEMS IN GRAPH EDGE COLORING

    信息来源: 发布日期:2023-05-22点击:

    时间 2023年5月22 日 14:30-15:30 报告人 陈冠涛(GEORGIA STATE UNIVERSITY(美国),教授、博士生导师)

    讲座题目OPTIMIZATION PROBLEMS IN GRAPH EDGE COLORING

    主办单位3522vip浦京集团官网

    报告专家:陈冠涛(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.


    地址:湖北荆州市南环路1号 | 邮编:434023 | 电话:(0716)8060182

    院长信箱:tzhang@yangtzeu.edu.cn | 学院办公室:sxxy@yangtzeu.edu.cn | 学生办公室:sxxg@yangtzeu.edu.cn

    版权所有©3522vip浦京集团(中國)官方网站     鄂ICP备05003301号-1 公网安备42100202000009号