{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:09Z","timestamp":1725488589931},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_13","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"118-125","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Minimum Cocolourings"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Christophe","family":"Novelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1002\/(SICI)1097-0118(199708)25:4<295::AID-JGT7>3.0.CO;2-F","volume":"25","author":"N. Alon","year":"1997","unstructured":"N. Alon, M. Krivelevich, AND B. Sudakov, Subgraphs with a large cochromatic number, J. Graph Theory, 25 (1997), pp. 295\u2013297.","journal-title":"J. Graph Theory"},{"key":"13_CR2","first-page":"263","volume":"22","author":"A. Brandst\u00e4dt","year":"1986","unstructured":"A. Brandst\u00e4dt AND D. Kratsch, On partitions of permutations into increasing and decreasing subsequences, Elektron. Informationsverarb. Kybernet., 22 (1986), pp. 263\u2013273.","journal-title":"Elektron. Informationsverarb. Kybernet."},{"key":"13_CR3","volume-title":"SIAM Monographs on Discrete Mathematics and Applications","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"A. Brandst\u00e4dt, V. B. Le, AND J. P. Spinrad, Graph classes: a survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia, 1999."},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/jgt.3190130106","volume":"13","author":"I. Broere","year":"1989","unstructured":"I. Broere AND M. Burger, Critically cochromatic graphs, J. Graph Theory, 13 (1989), pp. 23\u201328.","journal-title":"J. Graph Theory"},{"key":"13_CR5","unstructured":"J. Cheriyan AND R. Ravi, Approximation algorithms for network problems, 1998, manuscript."},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0167-5060(08)70393-5","volume-title":"Quo vadis, graph theory?","author":"P. Erd\u0151s","year":"1993","unstructured":"P. Erd\u0151s AND J. Gimbel, Some problems and results in cochromatic theory, in Quo vadis, graph theory?, North-Holland, Amsterdam, 1993, pp. 261\u2013264."},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/jgt.3190150604","volume":"15","author":"P. Erd\u0151s","year":"1991","unstructured":"P. Erd\u0151s, J. Gimbel, AND D. Kratsch, Some extremal results in cochromatic and dichromatic theory, J. Graph Theory, 15 (1991), pp. 579\u2013585.","journal-title":"J. Graph Theory"},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/S0195-6698(13)80123-0","volume":"11","author":"P. Erd\u0151s","year":"1990","unstructured":"P. Erd\u0151s, J. Gimbel, AND H. J. Straight, Chromatic number versus cochromatic number in graphs with bounded clique number, European J. Combin., 11 (1990), pp. 235\u2013240.","journal-title":"European J. Combin."},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"U. Feige AND J. Kilian, Zero knowledge and the chromatic number, J. Comput. System Sci., 57 (1998), pp. 187\u2013199. Complexity 96\u2014The Eleventh Annual IEEE Conference on Computational Complexity(Philadelphia, PA).","journal-title":"J. Comput. System Sci."},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/0095-8956(80)90079-9","volume":"29","author":"A. Frank","year":"1980","unstructured":"A. Frank, On chain and antichain families of a partially ordered set, J. Combin. Theory Ser. B, 29 (1980), pp. 176\u2013184.","journal-title":"J. Combin. Theory Ser. B"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0166-218X(92)00121-2","volume":"48","author":"J. Gimbel","year":"1994","unstructured":"J. Gimbel, D. Kratsch, AND L. Stewart, On cocolourings and cochromatic numbers of graphs, Discrete Appl. Math., 48 (1994), pp. 111\u2013127.","journal-title":"Discrete Appl. Math."},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01788548","volume":"3","author":"J. Gimbel","year":"1987","unstructured":"J. Gimbel AND H. J. Straight, Some topics in cochromatic theory, Graphs Combin., 3 (1987), pp. 255\u2013265.","journal-title":"Graphs Combin."},{"key":"13_CR13","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0097-3165(76)90078-9","volume":"20","author":"C. Greene","year":"1976","unstructured":"C. Greene, Some partitions associated with a partially ordered set, J. Combinatorial Theory Ser. A, 20 (1976), pp. 69\u201379.","journal-title":"J. Combinatorial Theory Ser. A"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0097-3165(76)90077-7","volume":"20","author":"C. Greene","year":"1976","unstructured":"C. Greene AND D. J. Kleitman, The structure of Sperner k-families, J. Combinatorial Theory Ser. A, 20 (1976), pp. 41\u201368.","journal-title":"J. Combinatorial Theory Ser. A"},{"key":"13_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, AND A. Schrijver, Geometric algorithms and combinatorial optimization, Springer-Verlag, Berlin, 1988."},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9 (1974), pp. 256\u2013278. Fifth Annual ACM Symposium on the Theory of Computing (Austin, Tex., 1973).","journal-title":"J. Comput. System Sci."},{"key":"13_CR18","first-page":"39","volume":"3","author":"L. M. Lesniak-Foster","year":"1977","unstructured":"L. M. Lesniak-Foster AND H. J. Straight, The cochromatic number of a graph, Ars Combin., 3 (1977), pp. 39\u201345.","journal-title":"Ars Combin."},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz, On the ratio of optimal integral and fractional covers, Discrete Math., 13 (1975), pp. 383\u2013390.","journal-title":"Discrete Math."},{"key":"13_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1002\/jgt.3190040114","volume":"4","author":"H. J. Straight","year":"1980","unstructured":"H. J. Straight, Note on the cochromatic number of several surfaces, J. Graph Theory, 4 (1980), pp. 115\u2013117.","journal-title":"J. Graph Theory"},{"key":"13_CR21","first-page":"633","volume":"20","author":"K. Wagner","year":"1984","unstructured":"K. Wagner, Monotonic coverings of finite sets, Elektron. Informationsverarb. Kybernet., 20 (1984), pp. 633\u2013639.","journal-title":"Elektron. Informationsverarb. Kybernet."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T06:55:18Z","timestamp":1550732118000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}