{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T01:28:00Z","timestamp":1768699680671,"version":"3.49.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319905297","type":"print"},{"value":"9783319905303","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-90530-3_19","type":"book-chapter","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T07:23:53Z","timestamp":1524554633000},"page":"220-231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Vertex Coloring Without Monochromatic Triangles"],"prefix":"10.1007","author":[{"given":"Micha\u0142","family":"Karpi\u0144ski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krzysztof","family":"Piecuch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,25]]},"reference":[{"issue":"3","key":"19_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"issue":"2","key":"19_CR2","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s10878-011-9385-3","volume":"24","author":"P Angelini","year":"2012","unstructured":"Angelini, P., Frati, F.: Acyclically 3-colorable planar graphs. J. Comb. Optim. 24(2), 116\u2013130 (2012)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"19_CR3","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R Brooks","year":"1941","unstructured":"Brooks, R.: On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc. 37(2), 194\u2013197 (1941)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic for graphs I: recognizable of fiite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"3","key":"19_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"DP Dailey","year":"1980","unstructured":"Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discret. Math. 30(3), 289\u2013293 (1980)","journal-title":"Discret. Math."},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Deb R.: An efficient nonparametric test of the collective household model (2008). SSRN: http:\/\/ssrn.com\/abstract=1107246","DOI":"10.2139\/ssrn.1107246"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Dinur, I., Regev, O., Smyth, C.: The hardness of 3-uniform hypergraph coloring. In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 33\u201340 (2002)","DOI":"10.1109\/SFCS.2002.1181880"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P Erdos","year":"1959","unstructured":"Erdos, P.: Graph thoery and probability. Canad. J. Math. 11, 34\u201338 (1959)","journal-title":"Canad. J. Math."},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"2513","DOI":"10.1016\/j.tcs.2010.10.043","volume":"412","author":"J Fiala","year":"2011","unstructured":"Fiala, J., Golovach, P., Kratochv\u00edl, J.: Parametrized complexity of coloring problems: treewidth versus vertex cover. Theor. Comput. Sci. 412, 2513\u20132523 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"19_CR10","doi-asserted-by":"crossref","first-page":"223","DOI":"10.2478\/v10209-011-0012-y","volume":"37","author":"P Formanowicz","year":"2012","unstructured":"Formanowicz, P., Tana\u015b, K.: A survey of graph coloring - its types, methods and applications. Found. Comput. Decis. Sci. 37(3), 223\u2013238 (2012)","journal-title":"Found. Comput. Decis. Sci."},{"key":"19_CR11","unstructured":"Jain, P.: On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem. Pre-print: arXiv:1003.3704 [cs.CC] (2010)"},{"issue":"1","key":"19_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/jgt.10167","volume":"46","author":"T Kaiser","year":"2004","unstructured":"Kaiser, T., \u0160krekovski, R.: Planar graph colorings without short monochromatic cycles. J. Graph Theory 46(1), 25\u201338 (2004)","journal-title":"J. Graph Theory"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.tcs.2016.10.011","volume":"659","author":"M Karpi\u0144ski","year":"2017","unstructured":"Karpi\u0144ski, M.: Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete. Theor. Comput. Sci. 659, 88\u201394 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Karpi\u0144ski, M., Piecuch, K.: On vertex coloring without monochromatic triangles. Pre-print, arXiv:1710.07132 [cs.DS] (2017)","DOI":"10.1007\/978-3-319-90530-3_19"},{"issue":"26\u201328","key":"19_CR15","doi-asserted-by":"publisher","first-page":"2619","DOI":"10.1016\/j.tcs.2010.02.015","volume":"411","author":"K Kawarabayashi","year":"2010","unstructured":"Kawarabayashi, K., Ozeki, K.: A simple algorithm for 4-coloring 3-colorable planar graphs. Theor. Comput. Sci. 411(26\u201328), 2619\u20132622 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"19_CR16","doi-asserted-by":"publisher","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","volume":"3","author":"J Mycielski","year":"1955","unstructured":"Mycielski, J.: Sur le coloriage des graphs. Colloquium Mathematicae 3(2), 161\u2013162 (1955)","journal-title":"Colloquium Mathematicae"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.tcs.2017.02.005","volume":"674","author":"Y Shitov","year":"2017","unstructured":"Shitov, Y.: A tractable NP-completeness proof for the two-coloring without monochromatic cycles of fixed length. Theor. Comput. Sci. 674, 116\u2013118 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"19_CR19","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.ipl.2005.12.007","volume":"98","author":"S Skulrattanakulchai","year":"2006","unstructured":"Skulrattanakulchai, S.: Delta-list vertex coloring in linear time. Inf. Process. Lett. 98(3), 101\u2013106 (2006)","journal-title":"Inf. Process. Lett."},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"1337","DOI":"10.1016\/j.jctb.2008.02.006","volume":"98","author":"C Thomassen","year":"2008","unstructured":"Thomassen, C.: 2-List-coloring planar graphs without monochromatic triangles. J. Comb. Theory Ser. B 98, 1337\u20131348 (2008)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-90530-3_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T22:09:52Z","timestamp":1751580592000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-90530-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319905297","9783319905303"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-90530-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"25 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Moscow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}