Top Qs
Timeline
Chat
Perspective
Goldberg–Seymour conjecture
From Wikipedia, the free encyclopedia
Remove ads
In graph theory, the Goldberg–Seymour conjecture states that, for a multigraph [1][2]
where is the edge chromatic number of G, is its maximum degree, and
This above quantity is twice the arboricity of G. It is sometimes called the density of G.[2]
Here, G can be a multigraph and can have loops. For simple graphs, this result follows from Vizing's theorem.
Remove ads
Background
It is already known that for loopless G (but can have parallel edges):[2][3]
When does equality not hold? It does not hold for the Petersen graph. It is hard to find other examples. It is currently unknown whether there are any planar graphs for which equality does not hold.
This conjecture is named after Mark K. Goldberg of Rensselaer Polytechnic Institute[4] and Paul Seymour of Princeton University, who arrived to it independently of Goldberg.[3]
Remove ads
Announced proof
In 2019, an alleged proof was announced by Chen, Jing, and Zang in the paper.[3] Part of their proof was to find a suitable generalization of Vizing's theorem (which says that for simple graphs ) to multigraphs. In 2023, Jing[5] announced a new proof with a polynomial-time edge coloring algorithm achieving the conjectured bound.
Remove ads
See also
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads