The Goldberg-Seymour conjecture, in graph theory, states that for a multigraph G the edge chromatic number of G is at most the greater of one plus the maximum degree of G and the maximum, over all subgraphs H of G, of a density quantity built from the number of edges and vertices of H. The conjecture bounds how many colors are needed to properly color the edges of a multigraph so that no two edges sharing a vertex receive the same color.
Facts
StatementFor a multigraph G, the Goldberg-Seymour conjecture states that the edge chromatic number of G is at most the greater of one plus the maximum degree of G and a density quantity Gamma of G derived from the densest subgraph structure of G. 1 Progress Toward ResolutionThe conjecture is now considered proven. Chen, Jing and Zang announced a proof in 2019, and in 2023 Jing announced a further proof that also yields a polynomial time edge coloring algorithm achieving the conjectured bound. 1 Classification
Resolution Status Chronology
Resolved Year Prize Status
Prize Status (category) Connections
In Branch
Source Goldberg-Seymour Conjecture (Wikipedia)
Sources
1. Goldberg-Seymour Conjecture (Wikipedia)
Lead section
the Goldberg-Seymour conjecture states that, for a multigraph G
History section
an alleged proof was announced by Chen, Jing, and Zang
- In Branch: Graph Theory, Lead sentence
View the Source2. Goldberg-Seymour conjecture (Wikipedia)
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.