{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T05:02:22Z","timestamp":1649048542609},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Inter. Net."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p> The weighted-edge-coloring problem of an edge-weighted graph whose weights are between 0 and 1, consists in finding a coloring using as few colors as possible and satisfying the following constraints: the sum of weights of edges with the same color and incident to the same vertex must be at most 1. In 1991, Chung and Ross conjectured that if G is bipartite, then [Formula: see text] colors are always sufficient to weighted-edge-color (G,w), where [Formula: see text] is the maximum of the sums of the weights of the edges incident to a vertex. We prove this is true for edge-weighted graphs with multiple edges whose underlying graph is a tree. We further generalise this conjecture to non-bipartite graphs and prove the generalised conjecture for simple edge-weighted outerplanar graphs. Finally, we introduce a list version of this coloring together with the list-bin-packing problem, which allows us to obtain new results concerning the original coloring for a specific class of graphs, namely the k-weight-degenerate weighted graph. <\/jats:p>","DOI":"10.1142\/s0219265911002861","type":"journal-article","created":{"date-parts":[[2011,12,12]],"date-time":"2011-12-12T07:07:10Z","timestamp":1323673630000},"page":"109-124","source":"Crossref","is-referenced-by-count":0,"title":["WEIGHTED-EDGE-COLORING OF k-DEGENERATE GRAPHS AND BIN-PACKING"],"prefix":"10.1142","volume":"12","author":[{"given":"FLORIAN","family":"HUC","sequence":"first","affiliation":[{"name":"LPD, EPFL Station 14, CH-1015 Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,8]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1953.tb01433.x"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/060656413"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284716"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/26.216511"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00579-0"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"rf8","unstructured":"E. G.\u00a0Coffman\u00a0Jr, M. R.\u00a0Garey and D. S.\u00a0Johnson, Approximation algorithms for NP-hard problems (PWS Publishing Co., 1996)\u00a0p. 93."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/0220046"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/0218021"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796313921"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(03)00011-X"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579456"},{"key":"rf16","volume-title":"Approximation algorithms","author":"Vazirani V. V.","year":"2004"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02582936"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1011"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<376::AID-RSA10>3.0.CO;2-0"}],"container-title":["Journal of Interconnection Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219265911002861","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T13:18:31Z","timestamp":1565097511000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219265911002861"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":16,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2012,4,8]]},"published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1142\/S0219265911002861"],"URL":"https:\/\/doi.org\/10.1142\/s0219265911002861","relation":{},"ISSN":["0219-2659","1793-6713"],"issn-type":[{"value":"0219-2659","type":"print"},{"value":"1793-6713","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]}}}