English
管理与服务机构
湖南大学党委办公室、校长办公室 纪律检查委员会办公室(监察处) 党委巡察办公室 党委组织部 党委党校 党委宣传部(资讯办公室) 党委统战部 党委学生工作部 党委研究生工作部 党委保卫部 人民武装部 机关党委 财院校区党工委 离退休处党委 校工会 共青团湖南大学委员会 发展规划办 教务处 现代工程训练中心 研究生院 招生与就业引导处 科学技术研究院 社会科学处 人力资源处 计划财务处 人才工程办公室 资产管理中心 国际合作与交流处 监察处 审计处 实验室建设与设备管理处 后勤与房地产管理处 基本建设处 离退休处 法律事务办公室 档案与校史馆 财院校区管委会 校友工作办公室 校园信息化建设与管理办公室 图书馆 远程与继续金沙学院 空军选培办 湖南发展研究院 国家超级计算长沙中心 互联网信息服务研究中心 资产经营有限企业 出版社有限责任企业 期刊社 后勤服务总企业 校医院 普通金沙与继续金沙管理办公室 招标与采购中心 学生创新创业中心
金沙与研究机构
机械与运载工程学院 电气与信息工程学院 材料科学与工程学院 信息科学与工程学院 建筑学院 环境科学与工程学院 土木工程学院 设计艺术学院 化学化工学院 生物学院 数学学院 物理与微电子科学学院 经济与贸易学院 金融与统计学院 工商管理学院 法学院 马克思主义学院 资讯传播与影视艺术学院 金沙科学研究院 体育学院 中国语言文学学院 岳麓书院 外国语学院 国家高效磨削工程技术研究中心 汽车车身先进设计制造国家重点实验室 化学生物传感与计量学国家重点实验室 经济管理研究中心 机器人学院 公共管理学院 艺术金沙中心
校园生活
当前位置: 金沙电子娱乐网址 >> 校园生活 >> 学术活动 >> 学院讲座 >> 正文
统计数据 / lectrue notice
  • 排序 学院 发文量
    1 机械与运载工程学院 202
    2 物理与微电子科学学院 192
    3 岳麓书院 182
    4 化学化工学院 173
    5 材料科学与工程学院 88
    6 数学与计量经济学院 88
    7 土木工程学院 74
    8 信息科学与工程学院 68
    9 教务处 47
    10 建筑学院 40
  • 排序 学院 发文量
    11 生物学院 39
    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

时间: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

湖大抖音
湖大微信
湖大微博
XML 地图 | Sitemap 地图