教育与研究机构
校园生活
当前位置: 首页 >> 校园生活 >> 学术活动 >> 学院讲座 >> 正文
统计数据 / lectrue notice
  • 排序 学院 发文量
    1 机械与运载工程学院 191
    2 物理与微电子科学学院 188
    3 岳麓书院 178
    4 化学化工学院 173
    5 材料科学与工程学院 88
    6 数学与计量经济学院 87
    7 土木工程学院 74
    8 信息科学与工程学院 68
    9 教务处 47
    10 建筑学院 40
  • 排序 学院 发文量
    11 经济与贸易学院 38
    12 生物学院 38
    13 电气与信息工程学院 36
    14 工商管理学院 28
    15 外国语学院 15
    16 法学院 15
    17 新闻传播与影视艺术学院 9
    18 研究生院 8
    19 经济与管理研究中心 6
    20 马克思主义学院 5
    21 中国语言文学学院 4
数学院:The Goldberg-Seymour Conjecture
学术地点 数学学院425 主讲人 陈冠涛教授, Georgia State University
讲座时间 2019年12月27日10:30-11:30

报告题目:The Goldberg-Seymour Conjecture

报告人:陈冠涛教授, Georgia State University

时间:2019年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.

上一条:数学院:Mathematical Optimization and 5G Mobile Communication System Design
下一条:土木院:液态空气储能创造低碳未来 Liquid air energy storage for a low carbon future

湖大官网
湖大微信
湖大微博