{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:35:54Z","timestamp":1725536154020},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642033506"},{"type":"electronic","value":"9783642033513"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03351-3_11","type":"book-chapter","created":{"date-parts":[[2009,8,3]],"date-time":"2009-08-03T08:53:58Z","timestamp":1249289638000},"page":"92-104","source":"Crossref","is-referenced-by-count":1,"title":["Approximability Distance in the Space of H-Colourability Problems"],"prefix":"10.1007","author":[{"given":"Tommy","family":"F\u00e4rnqvist","sequence":"first","affiliation":[]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[]},{"given":"Johan","family":"Thapper","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01261315","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon, N.: Bipartite subgraph. Combinatorica\u00a016, 301\u2013311 (1996)","journal-title":"Combinatorica"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF01215914","volume":"17","author":"N. Alon","year":"1997","unstructured":"Alon, N., Krivelevich, M.: The concentration of the chromatic number of random graphs. Combinatorica\u00a017, 303\u2013313 (1997)","journal-title":"Combinatorica"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0012-365X(02)00490-9","volume":"260","author":"A. Berman","year":"2003","unstructured":"Berman, A., Zhang, X.-D.: Bipartite density of cubic graphs. Discrete Mathematics\u00a0260, 27\u201335 (2003)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"11_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02122551","volume":"8","author":"B. Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B.: The chromatic number of random graphs. Combinatorica\u00a08(1), 49\u201355 (1988)","journal-title":"Combinatorica"},{"issue":"419","key":"11_CR5","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1017\/S0305004100053056","volume":"80","author":"B. Bollob\u00e1s","year":"1976","unstructured":"Bollob\u00e1s, B., Erd\u00f6s, P.: Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society\u00a080(419), 419\u2013427 (1976)","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1002\/jgt.3190100407","volume":"10","author":"J. Bondy","year":"1986","unstructured":"Bondy, J., Locke, S.: Largest bipartite subgraphs in triangle-free graphs with maximum degree three. Journal of Graph Theory\u00a010, 477\u2013504 (1986)","journal-title":"Journal of Graph Theory"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0095-8956(03)00081-9","volume":"90","author":"O. Borodin","year":"2004","unstructured":"Borodin, O., Kim, S.-J., Kostochka, A., West, D.: Homomorphisms from sparse graphs with large girth. Journal of Combinatorial Theory, ser. B\u00a090, 147\u2013159 (2004)","journal-title":"Journal of Combinatorial Theory, ser. B"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.20096","volume":"28","author":"A. Coja-Oghlan","year":"2005","unstructured":"Coja-Oghlan, A., Moore, C., Sanwalani, V.: MAX k-CUT and approximating the chromatic number of random graphs. Random Structures and Algorithms\u00a028, 289\u2013322 (2005)","journal-title":"Random Structures and Algorithms"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1023\/B:JOCO.0000038911.67280.3f","volume":"8","author":"E. Klerk de","year":"2004","unstructured":"de Klerk, E., Pasechnik, D., Warners, J.: Approximate graph colouring and MAX-k-CUT algorithms based on the \u03b8 function. Journal of Combinatorial Optimization\u00a08, 267\u2013294 (2004)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"4","key":"11_CR10","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF01787638","volume":"7","author":"R. Dutton","year":"1991","unstructured":"Dutton, R., Brigham, R.: Edges in graphs with large girth. Graphs and Combinatorics\u00a07(4), 315\u2013321 (1991)","journal-title":"Graphs and Combinatorics"},{"key":"11_CR11","unstructured":"Dvo\u0159\u00e1k, Z., \u0160krekovski, R., Valla, T.: Planar graphs of odd-girth at least 9 are homomorphic to the Petersen graph. To appear in SIAM Journal on Discrete Mathematics"},{"key":"11_CR12","unstructured":"Engstr\u00f6m, R.: Approximability distances between circular complete graphs. Master\u2019s thesis, Link\u00f6ping University. LITH-IDA-EX-A\u201308\/062\u2013SE (2008)"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P. Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P.: Graph theory and probability. Canadian Journal of Mathematics\u00a011, 34\u201338 (1959)","journal-title":"Canadian Journal of Mathematics"},{"key":"11_CR14","first-page":"17","volume":"5","author":"P. Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P., R\u00e9nyi, A.: On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences\u00a05, 17\u201361 (1960)","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"issue":"1","key":"11_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A. Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica\u00a018(1), 67\u201381 (1997)","journal-title":"Algorithmica"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"11_CR17","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2004)"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1002\/jgt.3190060205","volume":"6","author":"G. Hophkins","year":"1982","unstructured":"Hophkins, G., Staton, W.: Extremal bipartite subgraphs of cubic triangle-free graphs. Journal of Graph Theory\u00a06, 115\u2013121 (1982)","journal-title":"Journal of Graph Theory"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Every 2-CSP allows nontrivial approximation. In: Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC 2005), pp. 740\u2013746 (2005)","DOI":"10.1145\/1060590.1060700"},{"key":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-74510-5_20","volume-title":"Computer Science \u2013 Theory and Applications","author":"P. Jonsson","year":"2007","unstructured":"Jonsson, P., Krokhin, A., Kuivinen, F.: Ruling out polynomial-time approximation schemes for hard constraint satisfaction problems. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol.\u00a04649, pp. 182\u2013193. Springer, Heidelberg (2007), http:\/\/www.dur.ac.uk\/andrei.krokhin\/papers\/hardgap.pdf"},{"key":"11_CR21","unstructured":"Kann, V., Khanna, S., Lagergren, J., Panconesi, A.: On the hardness of approximating MAX k-CUT and its dual. Chicago Journal of Theoretical Computer Science\u00a01997(2) (1997)"},{"key":"11_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/11841036_40","volume-title":"Algorithms \u2013 ESA 2006","author":"A. Kaporis","year":"2006","unstructured":"Kaporis, A., Kirousis, L., Stavropoulos, E.: Approximating almost all instances of Max-cut within a ratio above the H\u00e5stad threshold. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 432\u2013443. Springer, Heidelberg (2006)"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing (STOC 2002), pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"issue":"1","key":"11_CR24","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S. Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnel, R.: Optimal inapproximability results for MAX-CUT and other two-variable CSPs? SIAM Journal of Computing\u00a037(1), 319\u2013357 (2007)","journal-title":"SIAM Journal of Computing"},{"key":"11_CR25","first-page":"19","volume":"28","author":"H.-J. Lai","year":"2000","unstructured":"Lai, H.-J., Liu, B.: Graph homomorphism into an odd cycle. Bulletin of the Institute of Combinatorics and its Applications\u00a028, 19\u201324 (2000)","journal-title":"Bulletin of the Institute of Combinatorics and its Applications"},{"key":"11_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/11830924_18","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Langberg","year":"2006","unstructured":"Langberg, M., Rabani, Y., Swamy, C.: Approximation algorithms for graph homomorphism problems. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 176\u2013187. Springer, Heidelberg (2006)"},{"key":"11_CR27","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1002\/jgt.3190140206","volume":"14","author":"S. Locke","year":"1990","unstructured":"Locke, S.: A note on bipartite subgraphs of triangle-free regular graphs. Journal of Graph Theory\u00a014, 181\u2013185 (1990)","journal-title":"Journal of Graph Theory"},{"issue":"1","key":"11_CR28","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01375472","volume":"11","author":"T. \u0141uczak","year":"1991","unstructured":"\u0141uczak, T.: The chromatic number of random graphs. Combinatorica\u00a011(1), 45\u201354 (1991)","journal-title":"Combinatorica"},{"key":"11_CR29","first-page":"382","volume":"19","author":"D. Matula","year":"1972","unstructured":"Matula, D.: The employee party problem. Notices of the American Mathematical Society\u00a019, A \u2013 382 (1972)","journal-title":"Notices of the American Mathematical Society"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proceedings of the 40th annual ACM symposium on the Theory of Computing (STOC 2008), pp. 245\u2013254 (2008)","DOI":"10.1145\/1374376.1374414"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: How to round any CSP (2009) (manuscript)","DOI":"10.1109\/FOCS.2009.74"},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"\u0160\u00e1mal, R.: Fractional covering by cuts. In: Proceedings of the 7th International Colloquium on Graph Theory (ICGT 2005), pp. 455\u2013459 (2005)","DOI":"10.1016\/j.endm.2005.06.099"},{"key":"11_CR33","unstructured":"\u0160\u00e1mal, R.: On XY mappings. PhD thesis, Charles University in Prague (2006)"},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Max Cut and the smallest eigenvalue. CoRR, abs\/0806.1978 (2008)","DOI":"10.1145\/1536414.1536452"},{"key":"11_CR35","first-page":"436","volume":"48","author":"P. Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory. Matematicko Fizicki Lapok\u00a048, 436\u2013452 (1941)","journal-title":"Matematicko Fizicki Lapok"}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03351-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T02:23:40Z","timestamp":1685067820000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03351-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033506","9783642033513"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03351-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}