{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T08:12:31Z","timestamp":1769242351610,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642325113","type":"print"},{"value":"9783642325120","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_51","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T18:21:08Z","timestamp":1342808468000},"page":"603-614","source":"Crossref","is-referenced-by-count":12,"title":["A Sharper Local Lemma with Improved Applications"],"prefix":"10.1007","author":[{"given":"Kashyap","family":"Kolipaka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yixin","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"8","key":"51_CR1","doi-asserted-by":"publisher","first-page":"1375","DOI":"10.1016\/j.disc.2007.07.063","volume":"308","author":"N. Alon","year":"2008","unstructured":"Alon, N., Grytczuk, J.: Breaking the rhythm on graphs. Discrete Mathematics\u00a0308(8), 1375\u20131380 (2008)","journal-title":"Discrete Mathematics"},{"issue":"3-4","key":"51_CR2","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1002\/rsa.10057","volume":"21","author":"N. Alon","year":"2002","unstructured":"Alon, N., Grytczuk, J., Haluszczak, M., Riordan, O.: Nonrepetitive colorings of graphs. Random Struct. Algorithms\u00a021(3-4), 336\u2013346 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"51_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N.: A parallel algorithmic version of the Local Lemma. In: FOCS, pp. 586\u2013593 (1991)","DOI":"10.1002\/rsa.3240020403"},{"issue":"3","key":"51_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/rsa.3240020303","volume":"2","author":"N. Alon","year":"1991","unstructured":"Alon, N., McDiarmid, C., Reed, B.A.: Acyclic coloring of graphs. Random Struct. Algorithms\u00a02(3), 277\u2013288 (1991)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"51_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/jgt.1010","volume":"37","author":"N. Alon","year":"2001","unstructured":"Alon, N., Sudakov, B., Zaks, A.: Acyclic edge colorings of graphs. Journal of Graph Theory\u00a037(3), 157\u2013167 (2001)","journal-title":"Journal of Graph Theory"},{"issue":"4","key":"51_CR6","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J. Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the Lov\u00e1sz Local Lemma. i. Random Struct. Algorithms\u00a02(4), 343\u2013366 (1991)","journal-title":"Random Struct. Algorithms"},{"key":"51_CR7","first-page":"1","volume":"FirstView","author":"R. Bissacot","year":"2011","unstructured":"Bissacot, R., Fernndez, R., Procacci, A., Scoppola, B.: An improvement of the Lov\u00e1sz Local Lemma via cluster expansion. Combinatorics, Probability and Computing, FirstView, 1\u201311 (2011)","journal-title":"Combinatorics, Probability and Computing"},{"issue":"2","key":"51_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.disc.2006.06.017","volume":"307","author":"B. Bresar","year":"2007","unstructured":"Bresar, B., Grytczuk, J., Klavzar, S., Niwczyk, S., Peterin, I.: Nonrepetitive colorings of trees. Discrete Mathematics\u00a0307(2), 163\u2013172 (2007)","journal-title":"Discrete Mathematics"},{"key":"51_CR9","unstructured":"Czumaj, A., Scheideler, C.: Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lov\u00e1sz Local Lemma. In: SODA, pp. 30\u201339 (2000)"},{"key":"51_CR10","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.tcs.2005.01.004","volume":"339","author":"J.D. Currie","year":"2005","unstructured":"Currie, J.D.: Pattern avoidance: themes and variations. Theor. Comput. Sci.\u00a0339, 7\u201318 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"51_CR11","unstructured":"Dujmovic, V., Joret, G., Kozik, J., Wood, D.R.: Nonrepetitive colouring via entropy compression. CoRR, abs\/1112.5524 (2012)"},{"key":"51_CR12","unstructured":"Erd\u00f6s, P., Lov\u00e1sz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Hajnal, A., Rado, R., Sos, V.T. (eds.) Infinite and Finite Sets (to Paul Erdos on his 60th birthday), pp. 609\u2013627 (1975)"},{"issue":"2-3","key":"51_CR13","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0166-218X(91)90040-4","volume":"30","author":"P. Erd\u00f6s","year":"1991","unstructured":"Erd\u00f6s, P., Spencer, J.: Lopsided Lov\u00e1sz Local Lemma and latin transversals. Discrete Applied Mathematics\u00a030(2-3), 151\u2013154 (1991)","journal-title":"Discrete Applied Mathematics"},{"key":"51_CR14","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/BF02764716","volume":"14","author":"B. Gr\u00fcnbaum","year":"1973","unstructured":"Gr\u00fcnbaum, B.: Acyclic colorings of planar graphs. Israel Journal of Mathematics\u00a014, 390\u2013408 (1973)","journal-title":"Israel Journal of Mathematics"},{"key":"51_CR15","doi-asserted-by":"crossref","unstructured":"Grytczuk, J.: Nonrepetitive colorings of graphs: A survey. Int. J. Math. Mathematical Sciences 2007 (2007)","DOI":"10.1155\/2007\/74639"},{"issue":"19","key":"51_CR16","doi-asserted-by":"publisher","first-page":"4419","DOI":"10.1016\/j.disc.2007.08.039","volume":"308","author":"J. Grytczuk","year":"2008","unstructured":"Grytczuk, J.: Thue type problems for graphs, points, and numbers. Discrete Mathematics\u00a0308(19), 4419\u20134429 (2008)","journal-title":"Discrete Mathematics"},{"key":"51_CR17","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1088\/0305-4470\/20\/2\/037","volume":"20","author":"A.J. Guttmann","year":"1987","unstructured":"Guttmann, A.J.: Comment: Comment on \u2019the exact location of partition function zeros, a new method for statistical mechanics\u2019. Journal of Physics A Mathematical General\u00a020, 511\u2013512 (1987)","journal-title":"Journal of Physics A Mathematical General"},{"key":"51_CR18","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the Lovasz Local Lemma. In: FOCS, pp. 397\u2013406 (2010)","DOI":"10.1109\/FOCS.2010.45"},{"key":"51_CR19","doi-asserted-by":"crossref","unstructured":"Kolipaka, K.B.R., Szegedy, M.: Moser and Tardos meet Lov\u00e1sz. In: STOC, pp. 235\u2013244 (2011)","DOI":"10.1145\/1993636.1993669"},{"issue":"23","key":"51_CR20","doi-asserted-by":"publisher","first-page":"3063","DOI":"10.1016\/j.disc.2007.03.006","volume":"307","author":"R. Muthu","year":"2007","unstructured":"Muthu, R., Narayanan, N., Subramanian, C.R.: Improved bounds on acyclic edge colouring. Discrete Mathematics\u00a0307(23), 3063\u20133069 (2007)","journal-title":"Discrete Mathematics"},{"key":"51_CR21","doi-asserted-by":"crossref","unstructured":"Moser, R.A.: A constructive proof of the Lov\u00e1sz Local Lemma. In: STOC, pp. 343\u2013350 (2009)","DOI":"10.1145\/1536414.1536462"},{"key":"51_CR22","doi-asserted-by":"crossref","unstructured":"Molloy, M., Reed, B.A.: Further algorithmic aspects of the Local Lemma. In: STOC, pp. 524\u2013529 (1998)","DOI":"10.1145\/276698.276866"},{"key":"51_CR23","doi-asserted-by":"crossref","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general Lov\u00e1sz Local Lemma. J. ACM\u00a057(2) (2010)","DOI":"10.1145\/1667053.1667060"},{"key":"51_CR24","unstructured":"Ndreca, S., Procacci, A., Scoppola, B.: Improved bounds on coloring of graphs (2010)"},{"key":"51_CR25","unstructured":"Pegden, W.: An improvement of the Moser-Tardos algorithmic local lemma. CoRR, abs\/1102.2853 (2011)"},{"issue":"3","key":"51_CR26","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02579368","volume":"5","author":"J.B. Shearer","year":"1985","unstructured":"Shearer, J.B.: On a problem of Spencer. Combinatorica\u00a05(3), 241\u2013245 (1985)","journal-title":"Combinatorica"},{"key":"51_CR27","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0012-365X(77)90044-9","volume":"20","author":"J. Spencer","year":"1977","unstructured":"Spencer, J.: Asymptotic lower bounds for Ramsey functions. Discrete Mathematics\u00a020, 69\u201376 (1977)","journal-title":"Discrete Mathematics"},{"key":"51_CR28","unstructured":"Srinivasan, A.: Improved algorithmic versions of the Lov\u00e1sz Local Lemma. In: SODA, pp. 611\u2013620 (2008)"},{"issue":"1-2","key":"51_CR29","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1017\/S0963548305007182","volume":"15","author":"A.D. Scott","year":"2006","unstructured":"Scott, A.D., Sokal, A.D.: On dependency graphs and the lattice gas. Combinatorics, Probability & Computing\u00a015(1-2), 253\u2013279 (2006)","journal-title":"Combinatorics, Probability & Computing"},{"key":"51_CR30","first-page":"1","volume":"7","author":"A. Thue","year":"1906","unstructured":"Thue, A.: \u00dcber unendliche Zeichenreihen. Norske Vid Selsk. Skr. I. Mat. Nat. Kl. Christian\u00a07, 1\u201322 (1906)","journal-title":"Norske Vid Selsk. Skr. I. Mat. Nat. Kl. Christian"},{"key":"51_CR31","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1142\/S0129183199000401","volume":"10","author":"S. Todo","year":"1999","unstructured":"Todo, S.: Transfer-matrix study of negative-fugacity singularity of hard-core lattice gas. International Journal of Modern Physics C\u00a010, 517\u2013529 (1999)","journal-title":"International Journal of Modern Physics C"},{"key":"51_CR32","doi-asserted-by":"crossref","unstructured":"Wood, D.W.: The exact location of partition function zeros, a new method for statistical mechanics. Journal of Physics A: Mathematical and General\u00a018(15), L917 (1985)","DOI":"10.1088\/0305-4470\/18\/15\/003"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T08:37:38Z","timestamp":1642840658000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}