Proof of the Goldberg–Seymour conjecture on edge–colorings of multigraphs

Guantao Chen (), Guangming Jing () and Wenan Zang ()
Additional contact information
Guantao Chen: Georgia State University
Guangming Jing: West Virginia University
Wenan Zang: The University of Hong Kong

Journal of Combinatorial Optimization, 2025, vol. 50, issue 3, No 1, 91 pages

Abstract: Abstract 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 referred to as the fractional edge-coloring problem (FECP). 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)$$ be the density of G, defined by $$\begin{aligned} \Gamma (G)=\max \left\{ \frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hspace{5.69054pt}\textrm{and} \hspace{5.69054pt}\textrm{odd} \right\} , \end{aligned}$$ 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 early 1970s Goldberg and Seymour independently conjectured that $$\chi '(G) \le \max \{\Delta (G)+1, \, \lceil \Gamma (G) \rceil \}$$ . Over the past five decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated an important body of work. In this paper 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 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$$ , and thus FECP has a fascinating integer rounding property.

Keywords: Multigraph; Edge-coloring; Chromatic index; Maximum degree; Density (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01348-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:3:d:10.1007_s10878-025-01348-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01348-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().