{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T23:40:23Z","timestamp":1739922023735,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_15","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"182-193","source":"Crossref","is-referenced-by-count":1,"title":["On the Computational Complexity of the Forcing Chromatic Number"],"prefix":"10.1007","author":[{"given":"Frank","family":"Harary","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Slany","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"Blass, A., Gurevich, Y.: On the unique satisfiability problem. Information and Control\u00a055, 80\u201388 (1982)","journal-title":"Information and Control"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jcss.1995.1028","volume":"50","author":"R. Chang","year":"1995","unstructured":"Chang, R., Kadin, J., Rohatgi, P.: On unique satisfiability and the threshold behaviour of randomized reductions. J.\u00a0Comp. Syst. Sci.\u00a050, 359\u2013373 (1995)","journal-title":"J.\u00a0Comp. Syst. Sci."},{"key":"15_CR3","first-page":"161","volume":"25","author":"G. Chartrand","year":"1997","unstructured":"Chartrand, G., Gavlas, H., Vandell, R.C., Harary, F.: The forcing domination number of a graph. J. Comb. Math. Comb. Comput.\u00a025, 161\u2013174 (1997)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"15_CR4","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/BFb0073124","volume-title":"Graph theory. Proc. of the 1-st Southeast Asian Colloq.","author":"C.J. Colbourn","year":"1984","unstructured":"Colbourn, C.J., Colbourn, M.J., Stinson, D.R.: The computational complexity of recognizing critical sets. In: Graph theory. Proc. of the 1-st Southeast Asian Colloq., Singapore. Lecture Notes in Mathematics, vol.\u00a01073, pp. 248\u2013253. Springer, Heidelberg (1984)"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Crescenzi, P.: A short quide to approximation preserving reductions. In: Proc. of the 12th Ann. Conference on Computational Complexity, pp. 262\u2013272 (1997)","DOI":"10.1109\/CCC.1997.612321"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1017\/S0004972700017883","volume":"41","author":"K. Gray","year":"1990","unstructured":"Gray, K.: On the minimum number of blocks defining a design. Bull. Aust. Math. Soc.\u00a041, 97\u2013112 (1990)","journal-title":"Bull. Aust. Math. Soc."},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/BF01886093","volume":"25","author":"D.L. Greenwell","year":"1974","unstructured":"Greenwell, D.L., Lov\u00e1sz, L.: Applications of product colouring. Acta Math. Acad. Sci. Hung.\u00a025, 335\u2013340 (1974)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01192587","volume":"6","author":"F. Harary","year":"1991","unstructured":"Harary, F., Klein, D., \u017divkovi\u0107, T.: Graphical properties of polyhexes: Perfect matching vector and forcing. J.\u00a0Math. Chemistry\u00a06, 295\u2013306 (1991)","journal-title":"J.\u00a0Math. Chemistry"},{"key":"15_CR9","unstructured":"Harary, F., Slany, W., Verbitsky, O.: On the computational complexity of the forcing chromatic number (2004), E-print, http:\/\/arXiv.org\/abs\/cs.CC\/0406044"},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BFb0017131","volume-title":"Mathematical Foundations of Computer Science 1988","author":"L. Hemachandra","year":"1988","unstructured":"Hemachandra, L.: Structure of complexity classes: separations, collapses, and completeness. In: Chytil, M.P., Janiga, L., Koubek, V. (eds.) MFCS 1988. LNCS, vol.\u00a0324, pp. 59\u201373. Springer, Heidelberg (1988)"},{"key":"15_CR11","first-page":"461","volume-title":"Combinatorics, Graph Theory, and Algorithms","author":"M. Mahdian","year":"1999","unstructured":"Mahdian, M., Mahmoodian, E.S., Naserasr, R., Harary, F.: On defining sets of vertex colorings of the Cartesian product of a cycle with a complete graph. In: Alavi, Y., Lick, D.R., Schwenk, A. (eds.) Combinatorics, Graph Theory, and Algorithms, pp. 461\u2013467. New Issues Press, Kalamazoo (1999)"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/S0012-365X(96)00247-6","volume":"167-168","author":"E.S. Mahmoodian","year":"1997","unstructured":"Mahmoodian, E.S., Naserasr, R., Zaker, M.: Defining sets in vertex colorings of graphs and Latin rectangles. Discrete Math.\u00a0167-168, 451\u2013460 (1997)","journal-title":"Discrete Math."},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1145\/62.322435","volume":"31","author":"C. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.: On the complexity of unique solutions. J. of the ACM\u00a031, 392\u2013400 (1984)","journal-title":"J. of the ACM"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/BF01200119","volume":"3","author":"D. Ranjan","year":"1993","unstructured":"Ranjan, D., Chari, S., Rohatgi, P.: Improving known solutions is hard. Comput. Complexity\u00a03, 168\u2013185 (1993)","journal-title":"Comput. Complexity"},{"key":"15_CR15","series-title":"Lecture Notes in Computer Science","volume-title":"The Computational Complexity of Equivalence and Isomorphism Problems","year":"2000","unstructured":"Thierauf, T. (ed.): The Computational Complexity of Equivalence and Isomorphism Problems. LNCS, vol.\u00a01852. Springer, Heidelberg (2000)"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solution. Theor. Comp. Sci.\u00a047, 287\u2013300 (1986)","journal-title":"Theor. Comp. Sci."}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T23:09:47Z","timestamp":1739920187000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}