{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T04:17:30Z","timestamp":1771042650141,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:00:00Z","timestamp":1758844800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:00:00Z","timestamp":1758844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Given a multigraph\n                    <jats:inline-formula>\n                      <jats:tex-math>$$G=(V,E)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , the edge-coloring problem (ECP) is to color the edges of\n                    <jats:italic>G<\/jats:italic>\n                    with the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is referred to as the fractional edge-coloring problem (FECP). The optimal value of ECP (resp. FECP) is called the chromatic index (resp. fractional chromatic index) of\n                    <jats:italic>G<\/jats:italic>\n                    , denoted by\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\chi '(G)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    (resp.\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\chi ^*(G)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    ). Let\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\Delta (G)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    be the maximum degree of\n                    <jats:italic>G<\/jats:italic>\n                    and let\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\Gamma (G)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    be the density of\n                    <jats:italic>G<\/jats:italic>\n                    , defined by\n                    <jats:disp-formula>\n                      <jats:tex-math>$$\\begin{aligned} \\Gamma (G)=\\max \\left\\{ \\frac{2|E(U)|}{|U|-1}:\\,\\, U \\subseteq V, \\,\\, |U|\\ge 3 \\hspace{5.69054pt}\\textrm{and} \\hspace{5.69054pt}\\textrm{odd} \\right\\} , \\end{aligned}$$<\/jats:tex-math>\n                    <\/jats:disp-formula>\n                    where\n                    <jats:italic>E<\/jats:italic>\n                    (\n                    <jats:italic>U<\/jats:italic>\n                    ) is the set of all edges of\n                    <jats:italic>G<\/jats:italic>\n                    with both ends in\n                    <jats:italic>U<\/jats:italic>\n                    . Clearly,\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\max \\{\\Delta (G), \\, \\lceil \\Gamma (G) \\rceil \\}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is a lower bound for\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\chi '(G)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . As shown by Seymour,\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\chi ^*(G)=\\max \\{\\Delta (G), \\, \\Gamma (G)\\}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . In the early 1970s Goldberg and Seymour independently conjectured that\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\chi '(G) \\le \\max \\{\\Delta (G)+1, \\, \\lceil \\Gamma (G) \\rceil \\}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . Over the past five decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated an important body of work. In this paper we present a proof of this conjecture. Our result implies that, first, there are only two possible values for\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\chi '(G)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , so an analogue to Vizing\u2019s theorem on edge-colorings of simple graphs holds for multigraphs; second, although it is\n                    <jats:italic>NP<\/jats:italic>\n                    -hard in general to determine\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\chi '(G)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , we can approximate it within one of its true value, and find it exactly in polynomial time when\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\Gamma (G)&gt;\\Delta (G)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    ; third, every multigraph\n                    <jats:italic>G<\/jats:italic>\n                    satisfies\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\chi '(G)-\\chi ^*(G) \\le 1$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , and thus FECP has a fascinating integer rounding property.\n                  <\/jats:p>","DOI":"10.1007\/s10878-025-01348-6","type":"journal-article","created":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T19:51:24Z","timestamp":1758916284000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Proof of the Goldberg\u2013Seymour conjecture on edge\u2013colorings of multigraphs"],"prefix":"10.1007","volume":"50","author":[{"given":"Guantao","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guangming","family":"Jing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenan","family":"Zang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,26]]},"reference":[{"key":"1348_CR1","doi-asserted-by":"publisher","first-page":"161","DOI":"10.7146\/math.scand.a-11685","volume":"40","author":"L Andersen","year":"1977","unstructured":"Andersen L (1977) On edge-colorings of graphs. Math Scand 40:161\u2013175","journal-title":"Math Scand"},{"key":"1348_CR2","doi-asserted-by":"publisher","first-page":"2231","DOI":"10.1016\/j.disc.2016.03.025","volume":"339","author":"J Asplund","year":"2016","unstructured":"Asplund J, McDonald J (2016) On a limit of the method of Tashkinov trees for edge-coloring. Discrete Math 339:2231\u20132238","journal-title":"Discrete Math"},{"key":"1348_CR3","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jctb.2018.01.006","volume":"131","author":"G Chen","year":"2018","unstructured":"Chen G, Gao Y, Kim R, Postle L, Shan S (2018) Chromatic index determined by fractional chromatic index. J Combin Theory Ser B 131:85\u2013108","journal-title":"J Combin Theory Ser B"},{"key":"1348_CR4","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.jctb.2019.03.004","volume":"139","author":"G Chen","year":"2019","unstructured":"Chen G, Jing G (2019) Structural properties of edge-chromatic critical multigraphs. J Combin Theory Ser B 139:128\u2013162","journal-title":"J Combin Theory Ser B"},{"key":"1348_CR5","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10878-009-9232-y","volume":"21","author":"G Chen","year":"2009","unstructured":"Chen G, Yu X, Zang W (2009) Approximating the chromatic index of multigraphs. J Comb Optim 21:219\u2013246","journal-title":"J Comb Optim"},{"key":"1348_CR6","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/17M1147676","volume":"29","author":"X Chen","year":"2019","unstructured":"Chen X, Zang W, Zhao Q (2019) Densities, matchings, and fractional edge-colorings. SIAM J Optim 29:240\u2013261","journal-title":"SIAM J Optim"},{"key":"1348_CR7","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Maximum matching and a polyhedron with $$0,1$$-vertices. J Res Nat Bur Standards Sect B 69:125\u2013130","journal-title":"J Res Nat Bur Standards Sect B"},{"key":"1348_CR8","unstructured":"Favrholdt L, Stiebitz M, Toft B (2006) Graph edge colouring: Vizing\u2019s theorem and goldberg\u2019s conjecture, Preprint, 20, IMADA, University of Southern Denmark, 91 p"},{"key":"1348_CR9","first-page":"3","volume":"23","author":"M Goldberg","year":"1973","unstructured":"Goldberg M (1973) On multigraphs of almost maximal chromatic class. Diskret Analiz 23:3\u20137 (in Russian)","journal-title":"Diskret Analiz"},{"key":"1348_CR10","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1002\/jgt.3190080115","volume":"8","author":"M Goldberg","year":"1984","unstructured":"Goldberg M (1984) Edge-coloring of multigraphs: recoloring technique. J Graph Theory 8:123\u2013137","journal-title":"J Graph Theory"},{"key":"1348_CR11","unstructured":"Gupta R (1967) Studies in the Theory of Graphs, Ph.D. Thesis, Tata Institute of Fundamental Research, Bombay"},{"key":"1348_CR12","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.jctb.2019.02.005","volume":"138","author":"P Haxell","year":"2019","unstructured":"Haxell P, Krivelevich M, Kronenberg G (2019) Goldberg\u2019s conjecture is true for random multigraphs. J Combin Theory Ser B 138:314\u2013349","journal-title":"J Combin Theory Ser B"},{"key":"1348_CR13","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1002\/jgt.20571","volume":"69","author":"P Haxell","year":"2012","unstructured":"Haxell P, McDonald J (2012) On characterizing Vizing\u2019s edge-coloring bound. J Graph Theory 69:160\u2013168","journal-title":"J Graph Theory"},{"key":"1348_CR14","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0196-6774(86)90039-8","volume":"7","author":"D Hochbaum","year":"1986","unstructured":"Hochbaum D, Nishizeki T, Shmoys D (1986) A better than \u201cbest possible\u2019\u2019 algorithm to edge color multigraphs. J Alg 7:79\u2013104","journal-title":"J Alg"},{"key":"1348_CR15","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1980","unstructured":"Holyer I (1980) The NP-completeness of edge-colorings. SIAM J Comput 10:718\u2013720","journal-title":"SIAM J Comput"},{"key":"1348_CR16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0012-365X(74)90009-0","volume":"9","author":"I Jakobsen","year":"1974","unstructured":"Jakobsen I (1974) On critical graphs with chromatic index $$4$$. Discrete Math 9:265\u2013279","journal-title":"Discrete Math"},{"key":"1348_CR17","unstructured":"Jakobsen I (1975) On critical graphs with respect to edge-coloring, In: Infinite and Finite Sets (A. Hajnal, R. Rado, and V. S\u00f3s, eds.), Vol. II, pp. 927-934, North-Holland, Amsterdam"},{"key":"1348_CR18","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1017\/CBO9781139519793.018","volume-title":"Topics in chromatic graph theory","author":"T Jensen","year":"2015","unstructured":"Jensen T, Toft B (2015) Unsolved graph edge coloring problems. In: Beineke L, Wilson R (eds) Topics in chromatic graph theory. Cambridge University Press, Cambridge, pp 327\u2013357"},{"key":"1348_CR19","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1006\/jctb.1996.0067","volume":"68","author":"J Kahn","year":"1996","unstructured":"Kahn J (1996) Asymptotics of the chromatic index for multigraphs. J Combin Theory Ser B 68:233\u2013254","journal-title":"J Combin Theory Ser B"},{"key":"1348_CR20","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0095-8956(84)90022-4","volume":"36","author":"H Kierstead","year":"1984","unstructured":"Kierstead H (1984) On the chromatic index of multigraphs without large triangles. J Combin Theory Ser B 36:156\u2013160","journal-title":"J Combin Theory Ser B"},{"key":"1348_CR21","doi-asserted-by":"publisher","first-page":"1480","DOI":"10.1137\/060664793","volume":"22","author":"A Letchford","year":"2008","unstructured":"Letchford A, Reinelt G, Theis D (2008) Odd matching cut sets and $$b$$-matchings revisited. SIAM J Discrete Math 22:1480\u20131487","journal-title":"SIAM J Discrete Math"},{"key":"1348_CR22","doi-asserted-by":"crossref","unstructured":"Marcotte O (1990) On the chromatic index of multigraphs and a conjecture of Seymour, II, In: Polyhedral Combinatorics (W. Cook and P. Seymour, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 1:245\u2013279","DOI":"10.1090\/dimacs\/001\/20"},{"key":"1348_CR23","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1017\/CBO9781139519793.008","volume-title":"Topics in chromatic graph theory","author":"J McDonald","year":"2015","unstructured":"McDonald J (2015) Edge-colorings. In: Beineke L, Wilson R (eds) Topics in chromatic graph theory. Cambridge University Press, Cambridge, pp 94\u2013113"},{"key":"1348_CR24","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0167-6377(91)90003-8","volume":"10","author":"G Nemhauser","year":"1991","unstructured":"Nemhauser G, Park S (1991) A polyhedral approach to edge coloring. Oper Res Lett 10:315\u2013322","journal-title":"Oper Res Lett"},{"key":"1348_CR25","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1137\/0403035","volume":"3","author":"T Nishizeki","year":"1990","unstructured":"Nishizeki T, Kashiwagi K (1990) On the 1.1 edge-coloring of multigraphs. SIAM J Discrete Math 3:391\u2013410","journal-title":"SIAM J Discrete Math"},{"key":"1348_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"M Padberg","year":"1982","unstructured":"Padberg M, Rao R (1982) Odd minimum cutsets and $$b$$-matchings. Math Oper Res 7:67\u201380","journal-title":"Math Oper Res"},{"key":"1348_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02591725","volume":"29","author":"M Padberg","year":"1984","unstructured":"Padberg M, Wolsey L (1984) Fractional covers for forests and matchings. Math Program 29:1\u201314","journal-title":"Math Program"},{"key":"1348_CR28","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0012-365X(98)00356-2","volume":"202","author":"M Plantholt","year":"1999","unstructured":"Plantholt M (1999) A sublinear bound on the chromatic index of multigraphs. Discrete Math 202:201\u2013213","journal-title":"Discrete Math"},{"key":"1348_CR29","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1002\/jgt.21670","volume":"73","author":"M Plantholt","year":"2013","unstructured":"Plantholt M (2013) A combined logarithmic bound on the chromatic index of multigraphs. J Graph Theory 73:239\u2013259","journal-title":"J Graph Theory"},{"key":"1348_CR30","unstructured":"Scheide D (2007) Kantenf\u00e4rbungen von Multigraphen, Diploma Thesis, TU Ilmenau, Ilmenau"},{"key":"1348_CR31","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.jctb.2009.04.001","volume":"100","author":"D Scheide","year":"2010","unstructured":"Scheide D (2010) Graph edge coloring: Tashkinov trees and Goldberg\u2019s conjecture. J Combin Theory Ser B 100:68\u201396","journal-title":"J Combin Theory Ser B"},{"key":"1348_CR32","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver A (1986) Theory of Linear and Integer Programming. Wiley, New York"},{"key":"1348_CR33","volume-title":"Combinatorial optimization - Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization - Polyhedra and Efficiency. Springer, Berlin"},{"key":"1348_CR34","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1112\/plms\/s3-38.3.423","volume":"38","author":"P Seymour","year":"1979","unstructured":"Seymour P (1979) On multi-colorings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc London Math Soc 38:423\u2013460","journal-title":"Proc London Math Soc"},{"key":"1348_CR35","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1002\/sapm1949281148","volume":"28","author":"C Shannon","year":"1949","unstructured":"Shannon C (1949) A theorem on coloring lines of a network. J Math Phys 28:148\u2013151","journal-title":"J Math Phys"},{"key":"1348_CR36","volume-title":"Graph edge colouring: Vizing\u2019s theorem and Goldberg\u2019s conjecture","author":"M Stiebitz","year":"2012","unstructured":"Stiebitz M, Scheide D, Toft B, Favrholdt L (2012) Graph edge colouring: Vizing\u2019s theorem and Goldberg\u2019s conjecture. Wiley, Hoboken"},{"issue":"7","key":"1348_CR37","first-page":"72","volume":"1","author":"V Tashkinov","year":"2000","unstructured":"Tashkinov V (2000) On an algorithm for the edge coloring of multigraphs. Diskretn Anal Issled Oper Ser 1(7):72\u201385 (in Russian)","journal-title":"Diskretn Anal Issled Oper Ser"},{"key":"1348_CR38","first-page":"25","volume":"3","author":"V Vizing","year":"1964","unstructured":"Vizing V (1964) On an estimate of the chromatic class of a $$p$$-graph. Diskret Analiz 3:25\u201330 (in Russian)","journal-title":"Diskret Analiz"}],"updated-by":[{"DOI":"10.1007\/s10878-025-01372-6","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T00:00:00Z","timestamp":1766102400000}}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01348-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01348-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01348-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T14:10:49Z","timestamp":1767190249000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01348-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,26]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["1348"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01348-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,26]]},"assertion":[{"value":"5 August 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2025","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised andthe formatting errors has been corrected.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2025","order":7,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":8,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":9,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10878-025-01372-6","URL":"https:\/\/doi.org\/10.1007\/s10878-025-01372-6","order":10,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"23"}}