Goldberg–Seymour conjecture

The Goldberg–Seymour conjecture states that a multigraph’s edge-chromatic number is at most the larger of its maximum degree plus one and its maximum odd-set edge density.

Connect

Edge coloring: An assignment of colors to a graph’s edges in which incident edges receive different colors. The conjecture bounds the minimum number of colors needed for this assignment.
Matching: A set of graph edges no two of which share an endpoint. Each color class in a proper edge coloring is a matching.
Paul Seymour: A British mathematician known for major contributions to graph theory and combinatorics. Seymour formulated the conjecture independently in the 1970s.
List edge coloring: An edge-coloring problem in which each edge has its own list of permitted colors. List-coloring analogues ask whether comparable degree and density bounds persist under restricted color choices.
Multigraph: A graph in which multiple edges may join the same pair of vertices. The conjecture concerns edge coloring in graphs that may have parallel edges.
Odd cut: A set of edges crossing a vertex partition in which one side has odd cardinality. Odd cuts expose parity constraints that can force additional edge colors.
Mark K. Goldberg: A mathematician whose work includes a conjecture on the chromatic index of multigraphs. Goldberg independently proposed the bound that shares his name.
Fractional chromatic index: The minimum total weight of matchings needed to cover each edge to weight at least one. It provides a fractional benchmark for the integral chromatic-index bound.
Chromatic index: The minimum number of colors needed for a proper edge coloring of a graph. This is the edge-coloring quantity the conjecture seeks to bound.
Fractional edge coloring: A relaxation of edge coloring that assigns nonnegative weights to matchings to cover every edge. Its density bounds illuminate fractional constraints, though the conjecture concerns integral colorings.