In graph theory the Goldberg–Seymour conjecture states that[1][2]
\( {\displaystyle \chi '(G)\leq \max(\Delta (G)+1,\Gamma (G))} \)
where \({\displaystyle \chi '(G)} is the edge chromatic number of G and
\( {\displaystyle \Gamma (G)=\max _{H\subset G}{\frac {|E(H)|}{{\frac {1}{2}}(|V(H)|-1)}}} \)
Note this above quantity is twice the arboricity of G. It is sometimes called the density of G.[2]
Above G can be a multigraph (can have loops).
Background
It is already known that for loopless G (but can have parallel edges):[2][3]
\( {\displaystyle \chi '(G)\geq \max\{\Delta (G),\lceil \Gamma (G)\rceil \}.} \)
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 Paul Seymour of Princeton University, who arrived to it independently of Goldberg.[3]
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 \( {\displaystyle \chi '(G)\leq \Delta (G)+1}) \)to multigraphs.
See also
Petersen graph#Coloring
Fractional coloring
Graph coloring
References
"Problems in Graph Theory and Combinatorics". faculty.math.illinois.edu. Retrieved 2019-05-05.
(PDF) https://math.gsu.edu/gchen/files/PPT/Guangming_ALS.pdf. Missing or empty |title= (help)
Zang, Wenan; Jing, Guangming; Chen, Guantao (2019-01-29). "Proof of the Goldberg–Seymour Conjecture on Edge-Colorings of Multigraphs". arXiv:1901.10316v1.
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
