{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:31:06Z","timestamp":1725798666210},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_44","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"517-528","source":"Crossref","is-referenced-by-count":0,"title":["On Coloring Resilient Graphs"],"prefix":"10.1007","author":[{"given":"Jeremy","family":"Kun","sequence":"first","affiliation":[]},{"given":"Lev","family":"Reyzin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"44_CR1","first-page":"1","volume":"5","author":"M. Ackerman","year":"2009","unstructured":"Ackerman, M., Ben-David, S.: Clusterability: A theoretical study. Journal of Machine Learning Research - Proceedings Track\u00a05, 1\u20138 (2009)","journal-title":"Journal of Machine Learning Research - Proceedings Track"},{"key":"44_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-22935-0_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Arora","year":"2011","unstructured":"Arora, S., Ge, R.: New tools for graph coloring. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2011. LNCS, vol.\u00a06845, pp. 1\u201312. Springer, Heidelberg (2011)"},{"issue":"1-2","key":"44_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ipl.2011.10.006","volume":"112","author":"P. Awasthi","year":"2012","unstructured":"Awasthi, P., Blum, A., Sheffet, O.: Center-based clustering under perturbation stability. Inf. Process. Lett.\u00a0112(1-2), 49\u201354 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"44_CR4","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF01840398","volume":"5","author":"B. Berger","year":"1990","unstructured":"Berger, B., Rompel, J.: A better performance guarantee for approximate graph coloring. Algorithmica\u00a05(3), 459\u2013466 (1990)","journal-title":"Algorithmica"},{"issue":"5","key":"44_CR5","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1017\/S0963548312000193","volume":"21","author":"Y. Bilu","year":"2012","unstructured":"Bilu, Y., Linial, N.: Are stable instances easy? Combinatorics, Probability & Computing\u00a021(5), 643\u2013660 (2012)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"3","key":"44_CR6","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1145\/176584.176586","volume":"41","author":"A. Blum","year":"1994","unstructured":"Blum, A.: New approximation algorithms for graph coloring. J. ACM\u00a041(3), 470\u2013516 (1994)","journal-title":"J. ACM"},{"issue":"3","key":"44_CR7","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L. Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Applied Mathematics\u00a0127(3), 415\u2013429 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"44_CR8","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"D.P. Dailey","year":"1980","unstructured":"Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are np-complete. Discrete Mathematics\u00a030(3), 289\u2013293 (1980)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"44_CR9","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1137\/07068062X","volume":"39","author":"I. Dinur","year":"2009","unstructured":"Dinur, I., Mossel, E., Regev, O.: Conditional hardness for approximate coloring. SIAM J. Comput.\u00a039(3), 843\u2013873 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"44_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00453-001-0054-2","volume":"32","author":"D. Eppstein","year":"2002","unstructured":"Eppstein, D., Bern, M.W., Hutchings, B.L.: Algorithms for coloring quadtrees. Algorithmica\u00a032(1), 87\u201394 (2002)","journal-title":"Algorithmica"},{"issue":"1","key":"44_CR11","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S.: The complexity of near-optimal graph coloring. J. ACM\u00a023(1), 43\u201349 (1976)","journal-title":"J. ACM"},{"issue":"1","key":"44_CR12","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/S0895480100376794","volume":"18","author":"V. Guruswami","year":"2004","unstructured":"Guruswami, V., Khanna, S.: On the hardness of 4-coloring a 3-colorable graph. SIAM J. Discrete Math.\u00a018(1), 30\u201340 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"44_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: A still better performance guarantee for approximate graph coloring. Inf. Process. Lett.\u00a045(1), 19\u201323 (1993)","journal-title":"Inf. Process. Lett."},{"key":"44_CR14","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n\n                  1\u2009\u2212\u2009\u03b5\n                  . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"issue":"1","key":"44_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/jgt.20635","volume":"71","author":"C.T. Ho\u00e0ng","year":"2012","unstructured":"Ho\u00e0ng, C.T., Maffray, F., Mechebbek, M.: A characterization of b-perfect graphs. Journal of Graph Theory\u00a071(1), 95\u2013122 (2012)","journal-title":"Journal of Graph Theory"},{"doi-asserted-by":"crossref","unstructured":"Huang, S.: Improved hardness of approximating chromatic number. CoRR, abs\/1301.5216 (2013)","key":"44_CR16","DOI":"10.1007\/978-3-642-40328-6_17"},{"unstructured":"Kawarabayashi, K.I., Thorup, M.: Coloring 3-colorable graphs with o(n\n                  1\/5) colors. In: STACS, vol.\u00a025, pp. 458\u2013469 (2014)","key":"44_CR17"},{"unstructured":"Johnson, D.S.: Worst case behavior of graph coloring algorithms. In: Proc. 5th Southeastern Conf. on Comb., Graph Theory and Comput., pp. 513\u2013527 (1974)","key":"44_CR18"},{"doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","key":"44_CR19","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"44_CR20","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s004930070013","volume":"20","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Linial, N., Safra, S.: On the hardness of approximating the chromatic number. Combinatorica\u00a020(3), 393\u2013415 (2000)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Khot, S.: Improved inaproximability results for maxclique, chromatic number and approximate graph coloring. In: FOCS, pp. 600\u2013609 (2001)","key":"44_CR21","DOI":"10.1109\/SFCS.2001.959936"},{"issue":"2-3","key":"44_CR22","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D. Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics\u00a0126(2-3), 197\u2013221 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"44_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-45477-2_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Kr\u00e1l\u2019","year":"2001","unstructured":"Kr\u00e1l\u2019, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 254\u2013262. Springer, Heidelberg (2001)"},{"issue":"1","key":"44_CR24","first-page":"32","volume":"13","author":"V. Kumar","year":"1992","unstructured":"Kumar, V.: Algorithms for constraint-satisfaction problems: A survey. AI Magazine\u00a013(1), 32 (1992)","journal-title":"AI Magazine"},{"key":"44_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-41392-6_11","volume-title":"Algorithmic Game Theory","author":"J. Kun","year":"2013","unstructured":"Kun, J., Powers, B., Reyzin, L.: Anti-coordination games and stable graph colorings. In: V\u00f6cking, B. (ed.) SAGT 2013. LNCS, vol.\u00a08146, pp. 122\u2013133. Springer, Heidelberg (2013)"},{"key":"44_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/978-3-642-18381-2_32","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science","author":"M. Mihal\u00e1k","year":"2011","unstructured":"Mihal\u00e1k, M., Sch\u00f6ngens, M., \u0160r\u00e1mek, R., Widmayer, P.: On the complexity of the metric TSP under stability considerations. In: \u010cern\u00e1, I., Gyim\u00f3thy, T., Hromkovi\u010d, J., Jefferey, K., Kr\u00e1lovi\u0107, R., Vukoli\u0107, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol.\u00a06543, pp. 382\u2013393. Springer, Heidelberg (2011)"},{"key":"44_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-642-34106-9_17","volume-title":"Algorithmic Learning Theory","author":"L. Reyzin","year":"2012","unstructured":"Reyzin, L.: Data stability in clustering: A closer look. In: Bshouty, N.H., Stoltz, G., Vayatis, N., Zeugmann, T. (eds.) ALT 2012. LNCS, vol.\u00a07568, pp. 184\u2013198. Springer, Heidelberg (2012)"},{"issue":"4","key":"44_CR28","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"Wigderson, A.: Improving the performance guarantee for approximate graph coloring. J. ACM\u00a030(4), 729\u2013735 (1983)","journal-title":"J. ACM"},{"issue":"1","key":"44_CR29","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing\u00a03(1), 103\u2013128 (2007)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T15:16:18Z","timestamp":1558970178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}