{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T05:20:22Z","timestamp":1741324822742,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642215865"},{"type":"electronic","value":"9783642215872"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21587-2_6","type":"book-chapter","created":{"date-parts":[[2011,6,25]],"date-time":"2011-06-25T17:16:07Z","timestamp":1309022167000},"page":"50-59","source":"Crossref","is-referenced-by-count":0,"title":["Solving 3-Colouring via 2SAT"],"prefix":"10.1007","author":[{"given":"Guillermo","family":"De Ita","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C\u00e9sar","family":"Bautista","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis C.","family":"Altamirano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Kahale, N.: A spectral technique for coloring random 3-colorable graphs. SIAM Jour. Comput. 26(6), 1733\u20131748 (1997), http:\/\/www.research.att.com\/kahale\/papers\/jour.ps","DOI":"10.1137\/S0097539794270248"},{"issue":"2","key":"6_CR2","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R. Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289 n ). Journal of Algorithms\u00a054(2), 168\u2013204 (2005)","journal-title":"Journal of Algorithms"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Blum, A., Karger, D.: An O(n 3\/14)-coloring algorithm for 3-colorable graphs. Inf. Proc. Lett. 61(1), 49\u201353 (1997), http:\/\/www.cs.cmu.edu\/http:\/\/www.cs.cmu.edu\/avrim\/Papers\/color_new.ps.gz","DOI":"10.1016\/S0020-0190(96)00190-1"},{"key":"6_CR4","unstructured":"Bodlaender H.L., Kratsch D.: An exact algorithm for graph coloring with polynomial memory. Technical Report UU-CS-2006-015 (2006), http:\/\/www.cs.uu.nl"},{"key":"6_CR5","unstructured":"Byskov J.M.: Exact Algorithms for graph colouring and exact satisifiability. Phd thesis, University of Aarbus, Denmark (2005)"},{"key":"6_CR6","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"6_CR7","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. North-Holland, Amsterdam (2004)","edition":"2"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Greenhill, C.: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity (1999)","DOI":"10.1007\/PL00001601"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"6_CR10","volume-title":"Graphs, Algorithms, and Optimization","author":"K. William","year":"2005","unstructured":"William, K., Kreher Donald, L.: Graphs, Algorithms, and Optimization. Chapman & Hall\/CRC, Boca Raton (2005)"},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E. Lawler","year":"1976","unstructured":"Lawler, E.: A note on the complexity of the chromatic number problem. Information Processing Letters\u00a05, 66\u201367 (1976)","journal-title":"Information Processing Letters"},{"key":"6_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-17514-5_13","volume-title":"Algorithms and Computation","author":"J. Stacho","year":"2010","unstructured":"Stacho, J.: 3-Colouring AT-Free Graphs in Polynomial Time. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol.\u00a06507, pp. 144\u2013155. Springer, Heidelberg (2010)"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Vlasie, R.D.: Systematic generation of very hard cases for graph 3-colorability. In: Proc. 7th-IEEE Int. Conf. Tools with Artificial Intelligence, pp. 114\u2013119 (1995)","DOI":"10.1109\/TAI.1995.479412"},{"key":"6_CR14","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198510611.001.0001","volume-title":"Graphs, Colourings and the Four-colour Theorem","author":"R.A. Wilson","year":"2002","unstructured":"Wilson, R.A.: Graphs, Colourings and the Four-colour Theorem. Oxford University Press, Oxford (2002)"}],"container-title":["Lecture Notes in Computer Science","Pattern Recognition"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21587-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T17:42:26Z","timestamp":1741282946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21587-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642215865","9783642215872"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21587-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}