{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:57Z","timestamp":1725558957644},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241324"},{"type":"electronic","value":"9783540305590"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30559-0_32","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:01:42Z","timestamp":1278097302000},"page":"377-388","source":"Crossref","is-referenced-by-count":0,"title":["The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small"],"prefix":"10.1007","author":[{"given":"Dominique","family":"de Werra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Demange","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jerome","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0012-365X(89)90196-9","volume":"74","author":"M.O. Albertson","year":"1989","unstructured":"Albertson, M.O., Jamison, R.E., Hedetniemi, S.T., Locke, S.C.: The subchromatic number of a graph. Discrete Math.\u00a074, 33\u201349 (1989)","journal-title":"Discrete Math"},{"key":"32_CR2","volume-title":"Selected topics in graph theory","author":"L.W. Beineke","year":"1978","unstructured":"Beineke, L.W., White, A.T.: Selected topics in graph theory. Academic Press, London (1978)"},{"key":"32_CR3","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"Berge, C.: Graphs and Hypergraphs. North Holland, Amsterdam (1973)"},{"key":"32_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0166-218X(94)90009-4","volume":"55","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Jansen, K., Woeginger, G.J.: Scheduling with incompatible jobs. Discrete Appl. Math.\u00a055, 219\u2013232 (1994)","journal-title":"Discrete Appl. Math."},{"key":"32_CR5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.7151\/dmgt.1037","volume":"17","author":"M. Borowiecki","year":"1997","unstructured":"Borowiecki, M., Broere, I., Frick, M., Mihok, P., Semanisin, G.: Survey of hereditary properties of graphs. Discussiones Mathematicae-Graph Theory\u00a017, 5\u201350 (1997)","journal-title":"Discussiones Mathematicae-Graph Theory"},{"key":"32_CR6","first-page":"69","volume":"40","author":"M. Boudhar","year":"2000","unstructured":"Boudhar, M., Finke, G.: Scheduling on a batch machine with job compatibilities. Jorbel\u00a040, 69\u201380 (2000)","journal-title":"Jorbel"},{"key":"32_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/3-540-36379-3_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Broersma","year":"2002","unstructured":"Broersma, H., Fomin, F.V., Ne\u0161et\u0159il, J., Woeginger, G.J.: More about subcolorings (extended abstract). In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 68\u201379. Springer, Heidelberg (2002)"},{"doi-asserted-by":"crossref","unstructured":"Brooks, R.L.: On colouring the nodes of a network. In: Proc. Cambridge Phil. Soc., vol.\u00a037, pp. 194\u2013197 (1941)","key":"32_CR8","DOI":"10.1017\/S030500410002168X"},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1002\/jgt.3190110113","volume":"11","author":"J.L. Brown","year":"1987","unstructured":"Brown, J.L., Corneil, D.G.: On generalized graph colorings. J. Graph Theory\u00a011, 87\u201399 (1987)","journal-title":"J. Graph Theory"},{"key":"32_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-36379-3_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Demange","year":"2002","unstructured":"Demange, M., de Werra, D., Monnot, J., Paschos, V.T.: Weighted node coloring: When stable sets are expensive. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 114\u2013125. Springer, Heidelberg (2002)"},{"unstructured":"Dillon, M.R.: Conditionnal coloring, Ph.D. thesis, University of Colorado at Denver (1998)","key":"32_CR11"},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput.System Sci.\u00a057, 187\u2013199 (1998)","journal-title":"J. Comput.System Sci."},{"key":"32_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/3-540-45477-2_15","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Fiala","year":"2001","unstructured":"Fiala, J., Jansen, K., Le, V.B., Seidel, E.: Graph subcolorings: Complexity and algorithms. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 154\u2013165. Springer, Heidelberg (2001)"},{"unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. a guide to the theory of NP-completeness. Freeman, CA (1979)","key":"32_CR14"},{"unstructured":"Grotzsch, H.: Ein dreifarbensatz fur dreikreisfreie netze auf der kugel, Wiss. Z. Martin Luther Univ. Halle-Wittenberg, Math. Naturwiss Reihe 8, 109\u2013120 (1959)","key":"32_CR15"},{"key":"32_CR16","volume-title":"Proc. First Colo. Symp. graph theory","author":"F. Harary","year":"1985","unstructured":"Harary, F.: Conditional colorability in graphs, in Graphs and Applications. In: Harary, F., Maybee, J. (eds.) Proc. First Colo. Symp. graph theory. Wiley intersci., Publ, N.Y (1985)"},{"key":"32_CR17","first-page":"237","volume":"1","author":"L. Lov\u00e1sz","year":"1966","unstructured":"Lov\u00e1sz, L.: On decomposition of graphs. Stud. Sci. Math. Hung.\u00a01, 237\u2013238 (1966)","journal-title":"Stud. Sci. Math. Hung."},{"doi-asserted-by":"crossref","unstructured":"Mutzel, P., Odenthal, T., Scharbrodt, M.: The thickness of graphs: A survey (1998)","key":"32_CR18","DOI":"10.1007\/PL00007219"},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0167-6377(85)90042-2","volume":"4","author":"F. Rendl","year":"1985","unstructured":"Rendl, F.: On the complexity of decomposing matrices arising in satellite communication. Operations Research Letters\u00a04, 5\u20138 (1985)","journal-title":"Operations Research Letters"},{"doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. STOC, pp. 216\u2013226 (1978)","key":"32_CR20","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30559-0_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T17:59:57Z","timestamp":1559239197000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30559-0_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241324","9783540305590"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30559-0_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}