Seymour's r-graph conjecture
Status solved high confidence
Seymour's r-graph conjecture is a direct corollary of the Goldberg–Seymour conjecture: for any $r$-graph $G$, the condition $|\delta(X)| \ge r$ for every odd $X \subseteq V(G)$ forces $\Gamma(G) \le r$, so the Goldberg–Seymour bound $\chi'(G) \le \max\{\Delta(G)+1, \lceil\Gamma(G)\rceil\}$ reduces to $\chi'(G) \le r+1$. The Goldberg–Seymour conjecture was proved by Chen, Jing, and Zang (2019 preprint; journal version 2025), resolving Seymour's r-graph conjecture as an immediate consequence.
Cited literature (1)
-
Proves the Goldberg–Seymour conjecture χ'(G) ≤ max{Δ(G)+1, ⌈Γ(G)⌉} for all multigraphs G; since every r-graph satisfies Γ(G) ≤ r (the r-graph condition bounds subgraph density), this immediately yields χ'(G) ≤ r+1 for every r-graph, resolving Seymour's r-graph conjecture. The proof first appeared as arXiv:1901.10316 in 2019.
Reviewer notes. The implication 'Goldberg–Seymour ⟹ r-graph conjecture' is standard: r-regularity gives Δ(G)=r, and for any odd set X the r-graph condition |δ(X)|≥r forces 2|E(G[X])| ≤ r(|X|-1), bounding Γ(G) ≤ r. A search summary mentioned Scheide (2007) made this implication explicit, but the Scheide reference was not independently verified by WebFetch. The Chen-Jing-Zang proof of Goldberg-Seymour first appeared as arXiv:1901.10316 in 2019 and is now verified via the 2025 Journal of Combinatorial Optimization article, DOI 10.1007/s10878-025-01348-6. A related 2023 survey (arXiv:2308.15588, Jing) discusses the Goldberg–Seymour conjecture algorithmically but did not explicitly mention the r-graph conjecture in the retrievable content.
Discussion
This conjecture is among the most important unsolved problems in edge coloring. It is very close in nature to Goldberg's Conjecture , and is also closely related to Rizzi's packing postman sets conjecture (see packing T-joins ). If $ G $ is an $ r $ -regular graph and there exists $ X \subseteq V(G) $ with $ |X| $ odd and $ |\delta(X)| < r $ , then it is immediate that $ G $ is not $ r $ -edge-colourable, since every perfect matching must use at least one edge from $ \delta(X) $ . This is in some sense the only obvious obstruction to $ r $ -edge-colorability that we know of. So, $ r $ -graphs are the $ r $ -regular graphs which do not fail to be $ r $ -edge-colorable for this obvious reason. Not every $ r $ -graph is $ r $ -edge-colorable, for instance Petersen's graph is a 3-graph which is not 3-edge-colorable. However, this conjecture asserts that all such graphs are still $ (r+1) $ -edge-colorable. This conjecture has been proved for $ r \le 11 $ by Nishizeki and Kashiwagi [NK].
Bibliography
-
[NK]T. Nishizeki and K. Kashiwagi, An upper bound on the chromatic index of multigraphs. Graph theory with applications to algorithms and computer science (Kalamazoo, Mich., 1984), 595--604, Wiley-Intersci. Publ., Wiley, New York, 1985. MathSciNet . MathSciNet -
★
[S]P.D. Seymour, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. London Math. Soc. (3) 38 (1979), no. 3, 423--460. MathSciNet . MathSciNet