Document Type
Lecture
Publication Date
9-11-2019
Abstract
Given a multigraph G = (VE), 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 (G) (resp. (G)). Let (G) be the maximum degree of G and let (G) = max 2E(U) U 1 : U V U 3andodd where E(U) is the set of all edges of G with both ends in U. Clearly, max (G) (G) is a lower bound for (G). As shown by Seymour, (G) = max (G) (G) . In the 1970s Goldberg and Seymour independently conjectured that (G) max (G) + 1 (G) . 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 (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 (G), we can approximate it within one of its true value, and find it exactly in polynomial time when (G) > (G); third, every multigraph G satisfies (G) (G) 1, so FECP has a fascinating integer rounding property. This is joint work with Guangming Jing and Wenan Zang.
Relational Format
presentation
Recommended Citation
Chen, Guantao, "The Goldberg-Seymour Conjecture" (2019). Combinatorics Seminar. 20.
https://egrove.olemiss.edu/math_combinatorics/20
