{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T15:00:18Z","timestamp":1767193218073},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,5,29]],"date-time":"2009-05-29T00:00:00Z","timestamp":1243555200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s10878-009-9232-y","type":"journal-article","created":{"date-parts":[[2009,5,28]],"date-time":"2009-05-28T18:20:37Z","timestamp":1243534837000},"page":"219-246","source":"Crossref","is-referenced-by-count":11,"title":["Approximating the chromatic index of multigraphs"],"prefix":"10.1007","volume":"21","author":[{"given":"Guantao","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xingxing","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Wenan","family":"Zang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,29]]},"reference":[{"key":"9232_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.7146\/math.scand.a-11685","volume":"40","author":"LD Andersen","year":"1977","unstructured":"Andersen LD (1977) On edge-colorings of graphs. Math Scand 40:161\u2013175","journal-title":"Math Scand"},{"key":"9232_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0020-0190(98)00138-0","volume":"68","author":"A Caprara","year":"1998","unstructured":"Caprara A, Rizzi R (1998) Improving a family of approximation algorithms to edge color multigraphs. Inf Process Lett 68:11\u201315","journal-title":"Inf Process Lett"},{"key":"9232_CR3","first-page":"125","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Maximum matching and a polyhedron with 0,1-vertices. J\u00a0Res Natl Bur Stand\u00a0B 69:125\u2013130","journal-title":"J\u00a0Res Natl Bur Stand\u00a0B"},{"key":"9232_CR4","unstructured":"Favrholdt LM, Stiebitz M, Toft B (2006) Graph edge colouring: Vizing\u2019s theorem and Goldberg\u2019s conjecture. http:\/\/bib.mathematics.dk\/preprint.php?lang=en&id=IMADA-PP-2006-20"},{"key":"9232_CR5","first-page":"3","volume":"23","author":"MK Goldberg","year":"1973","unstructured":"Goldberg MK (1973) On multigraphs of almost maximal chromatic class. Discret Anal 23:3\u20137 (in Russian)","journal-title":"Discret Anal"},{"key":"9232_CR6","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/jgt.3190080115","volume":"8","author":"MK Goldberg","year":"1984","unstructured":"Goldberg MK (1984) Edge-coloring of multigraphs: recoloring technique. J\u00a0Graph Theory 8:123\u2013137","journal-title":"J\u00a0Graph Theory"},{"key":"9232_CR7","unstructured":"Gupta RP (1967) Studies in the theory of graphs. PhD\u00a0thesis, Tata Institute of Fundamental Research, Bombay"},{"key":"9232_CR8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0196-6774(86)90039-8","volume":"7","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum DS, Nishizeki T, Shmoys DB (1986) A\u00a0better than \u201cbest possible\u201d algorithm to edge color multigraphs. J\u00a0Algorithms 7:79\u2013104","journal-title":"J\u00a0Algorithms"},{"key":"9232_CR9","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"IJ Holyer","year":"1980","unstructured":"Holyer IJ (1980) The NP-completeness of edge-colorings. SIAM J Comput 10:718\u2013720","journal-title":"SIAM J Comput"},{"key":"9232_CR10","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032497","volume-title":"Graph Coloring Problems","author":"TR Jensen","year":"1994","unstructured":"Jensen TR, Toft B (1994) Graph Coloring Problems. Wiley, New York"},{"key":"9232_CR11","doi-asserted-by":"crossref","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\u00a0Comb Theory Ser\u00a0B 68:233\u2013254","journal-title":"J\u00a0Comb Theory Ser\u00a0B"},{"key":"9232_CR12","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0095-8956(84)90022-4","volume":"36","author":"HA Kierstead","year":"1984","unstructured":"Kierstead HA (1984) On the chromatic index of multigraphs without large triangles. J\u00a0Comb Theory Ser\u00a0B 36:156\u2013160","journal-title":"J\u00a0Comb Theory Ser\u00a0B"},{"key":"9232_CR13","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/0095-8956(86)90053-5","volume":"41","author":"O Marcotte","year":"1986","unstructured":"Marcotte O (1986) On the chromatic index of multigraphs and a conjecture of Seymour,\u00a0I. J\u00a0Comb Theory Ser\u00a0B 41:306\u2013331","journal-title":"J\u00a0Comb Theory Ser\u00a0B"},{"key":"9232_CR14","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"235","volume-title":"Polyhedral Combinatorics","author":"O Marcotte","year":"1990","unstructured":"Marcotte O (1990) Exact edge-colorings of graphs without prescribed minors. In: Cook\u00a0W, Seymour\u00a0P (eds) Polyhedral Combinatorics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol\u00a01. Am. Math. Soc., Providence, pp\u00a0235\u2013243"},{"key":"9232_CR15","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"245","volume-title":"Polyhedral Combinatorics","author":"O Marcotte","year":"1990","unstructured":"Marcotte O (1990) On the chromatic index of multigraphs and a conjecture of Seymour,\u00a0II. In: Cook\u00a0W, Seymour\u00a0P (eds) Polyhedral Combinatorics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol\u00a01. Am. Math. Soc., Providence, pp\u00a0245\u2013279"},{"key":"9232_CR16","doi-asserted-by":"crossref","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":"9232_CR17","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1112\/jlms\/s2-44.3.393","volume":"44","author":"MJ Plantholt","year":"1991","unstructured":"Plantholt MJ, Tipnis SK (1991) Regular multigraphs of high degree are 1-factorable. J\u00a0Lond Math Soc 44:393\u2013400","journal-title":"J\u00a0Lond Math Soc"},{"key":"9232_CR18","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0012-365X(98)00356-2","volume":"202","author":"MJ Plantholt","year":"1999","unstructured":"Plantholt MJ (1999) A\u00a0sublinear bound on the chromatic index of multigraphs. Discrete Math 202:201\u2013213","journal-title":"Discrete Math"},{"key":"9232_CR19","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1145\/1361192.1361198","volume":"4","author":"P Sanders","year":"2008","unstructured":"Sanders P, Steurer D (2008) An asymptotic approximation scheme for multigraph edge coloring. ACM Trans Algorithms 4:897\u2013906","journal-title":"ACM Trans Algorithms"},{"key":"9232_CR20","unstructured":"Scheide D (2007) On the 15\/14 edge-colouring of multigraphs. http:\/\/bib.mathematics.dk\/unzip.php?filename=DMF-2007-09-007-v1.ps.gz"},{"key":"9232_CR21","volume-title":"Combinatorial Optimization\u2014Polyhedra and Efficiency, Volume\u00a0A","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial Optimization\u2014Polyhedra and Efficiency, Volume\u00a0A. Springer, Berlin"},{"key":"9232_CR22","first-page":"148","volume":"28","author":"C Shannon","year":"1949","unstructured":"Shannon C (1949) A theorem on coloring lines of a network. J\u00a0Math Phys 28:148\u2013151","journal-title":"J\u00a0Math Phys"},{"key":"9232_CR23","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1112\/plms\/s3-38.3.423","volume":"38","author":"PD Seymour","year":"1979","unstructured":"Seymour PD (1979) On multi-colorings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc Lond Math Soc 38:423\u2013460","journal-title":"Proc Lond Math Soc"},{"key":"9232_CR24","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF02128672","volume":"4","author":"PD Seymour","year":"1990","unstructured":"Seymour PD (1990) Colouring series-parallel graphs. Combinatorica 4:379\u2013392","journal-title":"Combinatorica"},{"key":"9232_CR25","first-page":"72","volume":"7","author":"VA Tashkinov","year":"2000","unstructured":"Tashkinov VA (2000) On an algorithm for the edge coloring of multigraphs. Diskret Anal Issled Oper Ser\u00a01 7:72\u201385 (in Russian)","journal-title":"Diskret Anal Issled Oper Ser\u00a01"},{"key":"9232_CR26","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing VG (1964) On an estimate of the chromatic class of a p-graph. Discret Anal 3:25\u201330 (in\u00a0Russian)","journal-title":"Discret Anal"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9232-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9232-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9232-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9232-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,29]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9232"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9232-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,29]]}}}