校園生活
當前位置: 首頁 >> 校園生活 >> 學術活動 >> 學院講座 >> 正文
統計數據 / lectrue notice
  • 排序學院發文量
    1機械與運載工程學院191
    2物理與微電子科學學院188
    3岳麓書院178
    4化學化工學院173
    5材料科學與工程學院88
    6數學與計量經濟學院86
    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.

湖大官網
湖大微信