{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T01:39:14Z","timestamp":1648863554241},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,1,11]],"date-time":"2013-01-11T00:00:00Z","timestamp":1357862400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2013,1,11]],"date-time":"2013-01-11T00:00:00Z","timestamp":1357862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The Haj\u00f3s\u2019 Theorem (Wiss Z Martin Luther Univ Math-Natur Reihe, 10, pp 116\u2013117,\u00a01961) shows a necessary and sufficient condition for the chromatic number of a given graph <jats:inline-formula>\n              <jats:tex-math>$$G$$<\/jats:tex-math>\n            <\/jats:inline-formula> to be at least <jats:inline-formula>\n              <jats:tex-math>$$k$$<\/jats:tex-math>\n            <\/jats:inline-formula>: <jats:inline-formula>\n              <jats:tex-math>$$G$$<\/jats:tex-math>\n            <\/jats:inline-formula> must contain a <jats:inline-formula>\n              <jats:tex-math>$$k$$<\/jats:tex-math>\n            <\/jats:inline-formula>-constructible subgraph. A graph is <jats:inline-formula>\n              <jats:tex-math>$$k$$<\/jats:tex-math>\n            <\/jats:inline-formula>-constructible if it can be obtained from a complete graph of order <jats:inline-formula>\n              <jats:tex-math>$$k$$<\/jats:tex-math>\n            <\/jats:inline-formula> by successively applying a set of well-defined operations. Given a vertex-weighted graph <jats:inline-formula>\n              <jats:tex-math>$$G$$<\/jats:tex-math>\n            <\/jats:inline-formula> and a (proper) <jats:inline-formula>\n              <jats:tex-math>$$r$$<\/jats:tex-math>\n            <\/jats:inline-formula>-coloring <jats:inline-formula>\n              <jats:tex-math>$$c=\\{C_1, \\ldots , C_r\\}$$<\/jats:tex-math>\n            <\/jats:inline-formula> of <jats:inline-formula>\n              <jats:tex-math>$$G$$<\/jats:tex-math>\n            <\/jats:inline-formula>, the weight of a color class <jats:inline-formula>\n              <jats:tex-math>$$C_i$$<\/jats:tex-math>\n            <\/jats:inline-formula> is the maximum weight of a vertex colored <jats:inline-formula>\n              <jats:tex-math>$$i$$<\/jats:tex-math>\n            <\/jats:inline-formula> and the weight of <jats:inline-formula>\n              <jats:tex-math>$$c$$<\/jats:tex-math>\n            <\/jats:inline-formula> is the sum of the weights of its color classes. The objective of the <jats:sc>Weighted Coloring Problem<\/jats:sc>\u00a0[7] is, given a vertex-weighted graph <jats:inline-formula>\n              <jats:tex-math>$$G$$<\/jats:tex-math>\n            <\/jats:inline-formula>, to determine the minimum weight of a proper coloring of <jats:inline-formula>\n              <jats:tex-math>$$G$$<\/jats:tex-math>\n            <\/jats:inline-formula>, that is, its weighted chromatic number. In this article, we prove that the <jats:sc>Weighted Coloring Problem<\/jats:sc> admits a version of the Haj\u00f3s\u2019 Theorem and so we show a necessary and sufficient condition for the weighted chromatic number of a vertex-weighted graph <jats:inline-formula>\n              <jats:tex-math>$$G$$<\/jats:tex-math>\n            <\/jats:inline-formula> to be at least <jats:inline-formula>\n              <jats:tex-math>$$k$$<\/jats:tex-math>\n            <\/jats:inline-formula>, for any positive real <jats:inline-formula>\n              <jats:tex-math>$$k$$<\/jats:tex-math>\n            <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s13173-012-0098-y","type":"journal-article","created":{"date-parts":[[2013,1,10]],"date-time":"2013-01-10T05:48:14Z","timestamp":1357796894000},"page":"275-278","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Haj\u00f3s-like theorem for weighted coloring"],"prefix":"10.1007","volume":"19","author":[{"given":"J.","family":"Araujo","sequence":"first","affiliation":[]},{"given":"C.","family":"Linhares Sales","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,11]]},"reference":[{"key":"98_CR1","unstructured":"Araujo J, Linhares Sales C, Sau I (2010) Weighted coloring on $$p_4$$-sparse graphs. In: 11es Journ\u00e9es Doctorales en Informatique et R\u00e9seaux (Sophia Antipolis, Mar 2010)"},{"key":"98_CR2","doi-asserted-by":"crossref","unstructured":"Bondy JA, Murty USR (2008) Graph theory. Graduate texts in mathematics. Springer, Berlin","DOI":"10.1007\/978-1-84628-970-5"},{"key":"98_CR3","doi-asserted-by":"crossref","first-page":"896","DOI":"10.1007\/978-3-540-30551-4_76","volume":"3341","author":"D Werra","year":"2005","unstructured":"de Werra D, Demange M, Escoffier B, Monnot J, Paschos VT (2005) Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation. Lect Notes Comput Sci 3341:896\u2013907","journal-title":"Lect Notes Comput Sci"},{"key":"98_CR4","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-36379-3_11","volume":"2573","author":"M Demange","year":"2002","unstructured":"Demange M, de Werra D, Monnot J, Paschos VT (2002) Weighted node coloring: when stable sets are expensive. Lect Notes Comput Sci 2573:114\u2013125","journal-title":"Lect Notes Comput Sci"},{"key":"98_CR5","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ipl.2005.09.013","volume":"97","author":"B Escoffier","year":"2006","unstructured":"Escoffier B, Monnot J, Paschos VT (2006) Weighted coloring: futher complexity and approximability results. Inf Process Lett 97:98\u2013103","journal-title":"Inf Process Lett"},{"key":"98_CR6","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0012-365X(95)00350-6","volume":"152","author":"S Gravier","year":"1996","unstructured":"Gravier S (1996) A Haj\u00f3s-like theorem for list coloring. Discret Math 152:299\u2013302","journal-title":"Discret Math"},{"key":"98_CR7","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0020-0190(97)00002-1","volume":"61","author":"D Guan","year":"1997","unstructured":"Guan D, Zhu X (1997) A coloring problem for weighted graphs. Inf Process Lett 61:77\u201381","journal-title":"Inf Process Lett"},{"key":"98_CR8","first-page":"116","volume":"10","author":"G Haj\u00f3s","year":"1961","unstructured":"Haj\u00f3s G (1961) Uber eine konstruktion nicht n-farbbarer graphen. Wiss Z Martin Luther Univ Math-Natur Reihe 10:116\u2013117","journal-title":"Wiss Z Martin Luther Univ Math-Natur Reihe"},{"key":"98_CR9","first-page":"69","volume":"55","author":"D Hanson","year":"1986","unstructured":"Hanson D, Robinson GC, Toft B (1986) Remarks on the graph colour theorem of Haj\u00f3s. Cong Numer 55:69\u201376","journal-title":"Cong Numer"},{"key":"98_CR10","volume-title":"Graph coloring problems","author":"TR Jensen","year":"1995","unstructured":"Jensen TR, Toft B (1995) Graph coloring problems. Wiley-Interscience, New York"},{"key":"98_CR11","doi-asserted-by":"crossref","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85\u2013104","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"98_CR12","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/j.disc.2004.07.001","volume":"287","author":"D Kral","year":"2004","unstructured":"Kral D (2004) Haj\u00f3s\u2019 theorem for list coloring. Discrete Math 287:161\u2013163","journal-title":"Discrete Math"},{"key":"98_CR13","doi-asserted-by":"crossref","unstructured":"Mansfield A, Welsh D (1982) Some colouring problems and their complexity. In: Bollob\u00e1s B (ed) Graph theory, proceedings of the conference on graph theory, vol 62 of North-Holland mathematics studies. North-Holland, pp 159\u2013170","DOI":"10.1016\/S0304-0208(08)73557-6"},{"key":"98_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s00493-005-0005-7","volume":"25","author":"B Mohar","year":"2005","unstructured":"Mohar B (2005) Haj\u00f3s\u2019 theorem for colorings of edge-weighted graphs. Combinatorica 25:65\u201376","journal-title":"Combinatorica"},{"key":"98_CR15","volume-title":"The four color problem","author":"O Ore","year":"1967","unstructured":"Ore O (1967) The four color problem. Academic Press, New York"},{"key":"98_CR16","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1002\/(SICI)1097-0118(199712)26:4<211::AID-JGT5>3.0.CO;2-T","volume":"26","author":"A Urquhart","year":"1997","unstructured":"Urquhart A (1997) The graph constructions of Haj\u00f3s and Ore. J Graph Theory 26:211\u2013215","journal-title":"J Graph Theory"},{"key":"98_CR17","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s00373-002-0505-9","volume":"19","author":"X Zhu","year":"2003","unstructured":"Zhu X (2003) An analogue of Haj\u00f3s\u2019 theorem for the circular chromatic number (ii). Graphs Comb 19:419\u2013432","journal-title":"Graphs Comb"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0098-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-012-0098-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0098-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0098-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T21:13:42Z","timestamp":1630530822000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-012-0098-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,11]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["98"],"URL":"https:\/\/doi.org\/10.1007\/s13173-012-0098-y","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,11]]},"assertion":[{"value":"18 September 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}