{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T22:57:20Z","timestamp":1763765840788},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p> We study a weighted improper coloring problem motivated by a frequency allocation problem. It consists of associating to each vertex a set of p(v) (weight) distinct colors (frequencies), such that the set of vertices having a given color induces a graph of degree at most k (the case k = 0 corresponds to proper coloring). The objective is to minimize the number of colors. We propose approximation algorithms to compute such a coloring for general graphs. We apply these to obtain good approximation ratio for grid and hexagonal graphs. Furthermore we give exact results for the 2-dimensional grid and the triangular lattice when the weights are all the same. <\/jats:p>","DOI":"10.1142\/s1793830910000747","type":"journal-article","created":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T04:44:00Z","timestamp":1286858640000},"page":"395-411","source":"Crossref","is-referenced-by-count":6,"title":["IMPROPER COLORING OF WEIGHTED GRID AND HEXAGONAL GRAPHS"],"prefix":"10.1142","volume":"02","author":[{"given":"JEAN-CLAUDE","family":"BERMOND","sequence":"first","affiliation":[{"name":"Projet Mascotte I3S (CNRS &amp; UNS), 2004 route des Lucioles, BP 93, 06902, Sophia-Antipolis Cedex, France"},{"name":"INRIA, INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902, Sophia-Antipolis Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FR\u00c9D\u00c9RIC","family":"HAVET","sequence":"additional","affiliation":[{"name":"Projet Mascotte I3S (CNRS &amp; UNS), 2004 route des Lucioles, BP 93, 06902, Sophia-Antipolis Cedex, France"},{"name":"INRIA, INRIA Sophia-Antipolis, 2004 route des Lucioles, BP 93, 06902, Sophia-Antipolis Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FLORIAN","family":"HUC","sequence":"additional","affiliation":[{"name":"Centre Universitaire dInformatique, Battelle b\u00e2timent A route de Drize 7, 1227 Carouge Geneva, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CL\u00c1UDIA LINHARES","family":"SALES","sequence":"additional","affiliation":[{"name":"Universidade Federal do Cear\u00e1, Departamento de Computa\u00e7\u00e3o, Bloco 910, Campus do Pici, Fortaleza, Cear\u00e1 CEP 60455-760, Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00241-7"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2005.06.022"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1002\/net.20318"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00079-6"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-G"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.002"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000747","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T21:34:50Z","timestamp":1565127290000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000747"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":7,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1142\/S1793830910000747"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000747","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}