﻿ 20191227 陈冠涛 The Goldberg-Seymour Conjecture-湖南大学数学学院

# 20191227 陈冠涛 The Goldberg-Seymour Conjecture

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.