Goldberg–Seymour Theorem

Every loopless multigraph can be properly edge-colored using no more than the larger of maximum degree plus one and the ceiling of its densest odd-set edge ratio.

Version

v3 · 2026-09-19 · History

Domain-specific #

1942

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomains

Graph Theory, Multigraph Edge Coloring → Mathematics

Aliases

Goldberg Seymour Conjecture, Goldberg Conjecture on Edge Coloring, Seymour Edge Coloring Conjecture

Core Idea

The Goldberg–Seymour Theorem, historically known as the Goldberg–Seymour Conjecture, states that the chromatic index of a loopless multigraph is controlled to within one color by two unavoidable obstructions: congestion at a vertex and congestion inside an odd vertex set. For a loopless multigraph (G=(V,E)), let \(\chi'(G)\) be the minimum number of colors in a proper edge coloring and \(\Delta(G)\) its maximum degree. Define the odd-set density

\[ \Gamma(G)=\max_{\substack{U\subseteq V\\ |U|\ge 3\;\text{odd}}} \frac{2|E(U)|}{|U|-1}, \]

How would you explain it like I'm…

Busy Dots, Crowded Clumps

Imagine dots joined by strings, and you paint each string so that no two strings touching the same dot share a color. A very busy dot needs lots of colors. A tight clump with an odd number of dots, packed with strings, can also need lots of colors. This theorem says you never need more than one extra color beyond what the busiest dot needs, unless a crowded odd clump needs even more, and then that clump's number is enough.

Only Two Coloring Troublemakers

A multigraph is a set of dots where two dots can be joined by several lines. You want to color the lines so that no two lines meeting at the same dot have the same color, using as few colors as possible. Two things force you to use many colors: a dot with lots of lines, since all of them need different colors, and an odd-sized group of dots packed with lines, because each color can only pair up dots inside that group, leaving one dot out. The Goldberg–Seymour Theorem says these are the only real troublemakers. You never need more than one color beyond the busiest dot, unless an odd crowded group demands more, and then that group's demand is enough.

Degree-or-Odd-Set Coloring Bound

In a multigraph (dots joined by possibly repeated edges, but no edge looping back to the same dot), a proper edge coloring gives edges that share an endpoint different colors. The minimum number of colors is the chromatic index. Two lower bounds are easy: a vertex of maximum degree Δ forces at least Δ colors, and an odd set of k vertices can host at most (k−1)/2 edges of any single color, so a dense odd set forces at least 2·(internal edges)/(k−1) colors, rounded up. The Goldberg–Seymour Theorem says the chromatic index is at most the larger of Δ+1 and that densest-odd-set bound. So the true answer is always within one color of what these two simple obstructions demand. It was a conjecture from the 1970s and now has a published proof.

 

Let G be a loopless multigraph with maximum degree Δ(G) and chromatic index χ'(G). Define the odd-set density Γ(G) as the maximum, over odd vertex subsets U with |U| ≥ 3, of 2|E(U)|/(|U|−1), where E(U) counts edges (with multiplicity) inside U. Both quantities give lower bounds: edges at a maximum-degree vertex are pairwise adjacent, so χ' ≥ Δ; and each color class is a matching, covering at most (|U|−1)/2 edges inside an odd U, so χ' ≥ ⌈Γ⌉. The Goldberg–Seymour Theorem gives the matching upper bound χ'(G) ≤ max{Δ+1, ⌈Γ⌉}. Consequently, the chromatic index is either the max of Δ and ⌈Γ⌉ or one more than that, so these two obstruction families are essentially complete. Beware a notational difference: some sources build the ceiling into the definition of Γ. Conjectured in related forms by Goldberg, Seymour and others in the 1970s, it was proved by Chen, Jing and Zang, with publication in 2025.

Scope of Application

The theorem applies to finite loopless multigraphs with arbitrary parallel-edge multiplicity. It includes simple graphs as a special case, but its distinctive content is the control of extra color demand created by dense odd submultigraphs. A proper edge coloring is equivalently a partition of the edge multiset into matchings, so the odd-set bound is a matching-capacity constraint.

The result tightly connects integral and fractional edge coloring. Seymour's fractional characterization gives

Clarity

Two density notations circulate. This draft uses real-valued \(\Gamma(G)=\max 2|E(U)|/(|U|-1)\) and writes the ceiling in coloring formulas. An alternative defines

\[ \Gamma_{\mathrm{int}}(G)= \max_{|U|\ge3\text{ odd}} \left\lceil\frac{2|E(U)|}{|U|-1}\right\rceil. \]

Because the maximum ranges over a finite family, \(\Gamma_{\mathrm{int}}=\lceil\Gamma\rceil\), but mixing symbols across conventions creates apparent discrepancies.

Manages Complexity

Without the theorem, parallel edges allow local degree alone to badly underdescribe color demand, and arbitrary subgraph structure appears relevant. Goldberg–Seymour compresses the obstruction landscape into two quantities: maximum vertex load and maximum odd-set load. Every other structural complication is bounded within one additional color of their envelope.

Abstract Reasoning

The odd-set lower bound follows by capacity counting. In any (k)-edge coloring, the edges of one color form a matching. For odd (U), a matching uses at most ((|U|-1)/2) edges of (E(U)). Across (k) colors,

\[ |E(U)|\le k\frac{|U|-1}{2}, \]

Knowledge Transfer

The theorem gives graph theorists, matching theorists, and optimization researchers a common dictionary among proper edge coloring, matching capacity, odd-set inequalities, fractional relaxation, integrality gap, and algorithms. It explains why matching-polytope structure enters an edge-coloring question and why maximum degree alone ceases to be sufficient for multigraphs.

Transfer outside this domain must preserve the exact conflict and capacity model. Scheduling tasks that share resources can be represented as edge coloring only when jobs are edges, resources are endpoints, and each time slot is a matching.

Relationships to Other Abstractions

Current abstraction Goldberg–Seymour Theorem Domain-specific

Parents (1) — outgoing typed relations

• Goldberg–Seymour Theorem is a kind of Graph Coloring Prime

  the theorem is a specialized universal result about conflict-free edge labels on multigraphs; this is the broader abstraction this entry instantiates.

Hierarchy path (1) — routes to 1 parentless root

• Goldberg–Seymour Theorem → is a kind of Graph Coloring → is a kind of Partition → presupposes Set and Membership

Neighborhood in Abstraction Space

Goldberg–Seymour Theorem sits in a sparse region of the domain-specific corpus (79^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Dense Graph — 0.84
• Cubic Graph — 0.83
• Fractional Coloring — 0.83
• Turán Graph — 0.83
• Edge Coloring — 0.82

Computed from structural-signature embeddings · 2026-10-25