银河娱乐平台

学术报告
您现在的位置: 首页 > 科学研究 > 学术报告 > 正文

20191227 陈冠涛 The Goldberg-Seymour Conjecture

发布时间:2019-12-20 14:25    浏览次数:    来源:

报告题目:The Goldberg-Seymour Conjecture
报告人:陈冠涛教授, Georgia State University
时间:12月27日10:30-11:30am
地点:数学学院425
摘要: Given a multigraph $G=(V,E)$, the  edge-coloring problem (ECP) is to color the edges of $G$ with the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer
program, and its linear programming relaxation is called the fractional edge-coloring problem (FECP). In the
literature, the optimal value of ECP (resp. FECP) is called the  chromatic index (resp.  fractional chromatic
index) of $G$, denoted by $\chi'(G)$ (resp. $\chi^*(G)$). Let $\Delta(G)$ be the maximum degree of $G$ and let
\[\Gamma(G)=\max \Big\{\frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hskip 2mm
{\rm and \hskip 2mm odd} \Big\},\]
where $E(U)$ is the set of all edges of $G$ with both ends in $U$.  Clearly, $\max\{\Delta(G), \,
\lceil \Gamma(G) \rceil \}$ is a lower bound for $\chi'(G)$. As shown by Seymour, $\chi^*(G)=\max\{\Delta(G), \,
\Gamma(G)\}$. In the 1970s Goldberg and Seymour independently conjectured that $\chi'(G) \le \max\{\Delta(G)+1,
\, \lceil \Gamma(G) \rceil\}$. Over the past four decades this conjecture, a cornerstone in modern edge-coloring,
has been a subject of extensive research, and has stimulated a significant body of work.We present a proof of this conjecture. Our result implies that, first, there are only two possible values for $\chi'(G)$, so an analogue to Vizing's theorem on edge-colorings of simple graphs, a fundamental
result in graph theory, holds for multigraphs; second, although it is $NP$-hard in general to determine $\chi'(G)$,
we can approximate it within one of its true value, and find it exactly in polynomial time when $\Gamma(G)>\Delta(G)$;
third, every multigraph $G$ satisfies $\chi'(G)-\chi^*(G) \le 1$, so FECP has a fascinating integer rounding property.

2019银河在线娱乐平台|手机澳门银河娱乐平台 版权所有©2017年    通讯地址:湖南省长沙市岳麓区麓山南路麓山门     邮编:410082     Email:xiaoban@hnu.edu.cn
域名备案信息:[www.hnu.edu.cn,www.hnu.cn/湘ICP备05000239号]      [hnu.cn 湘教QS3-200503-000481 hnu.edu.cn  湘教QS4-201312-010059]