机关部处 群团组织 直附属机构
岳麓书院 经济与贸易学院 金融与统计学院 法学院 马克思主义学院 教育科学研究院 体育学院 中国语言文学学院 外国语学院 资讯与传播学院 数学学院 物理与微电子科学学院 化学化工学院 生物学院 机械与运载工程学院 材料科学与工程学院 电气与信息工程学院 信息科学与工程学院 建筑学院 土木工程学院 环境科学与工程学院 工商管理学院 公共管理学院 设计艺术学院 机器人学院 经济管理研究中心 化学生物传感与计量学国家重点实验室 国家高效磨削工程技术研究中心 汽车车身先进设计制造国家重点实验室 国家电能变换与控制国家工程技术研究中心 机器人视觉感知与控制技术国家工程实验室
当前位置: 澳门新葡8455最新网站 >> 校园生活 >> 学术活动 >> 学院讲座 >> 正文
统计数据 / lectrue notice
  • 排序 学院 发文量
    1 物理与微电子科学学院 211
    2 机械与运载工程学院 208
    3 岳麓书院 184
    4 化学化工学院 178
    5 材料科学与工程学院 90
    6 数学与计量经济学院 88
    7 土木工程学院 75
    8 信息科学与工程学院 68
    9 教务处 48
    10 建筑学院 40
  • 排序 学院 发文量
    11 生物学院 40
    12 经济与贸易学院 38
    13 电气与信息工程学院 36
    14 工商管理学院 28
    15 外国语学院 15
    16 法学院 15
    17 资讯传播与影视艺术学院 9
    18 研究生院 9
    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



摘要: 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

XML 地图 | Sitemap 地图