{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T20:18:26Z","timestamp":1743106706157,"version":"3.40.3"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319301389"},{"type":"electronic","value":"9783319301396"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-30139-6_17","type":"book-chapter","created":{"date-parts":[[2016,2,19]],"date-time":"2016-02-19T08:35:02Z","timestamp":1455870902000},"page":"209-221","source":"Crossref","is-referenced-by-count":1,"title":["Large Independent Sets in Subquartic Planar Graphs"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Mnich","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","unstructured":"Albertson, M., Bollobas, B., Tucker, S.: The independence ratio and maximum degree of a graph. In: Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 43\u201350. Congressus Numerantium, No. XVII. Utilitas Math., Winnipeg, Man. (1976)"},{"issue":"5","key":"17_CR2","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1090\/S0002-9904-1976-14122-5","volume":"82","author":"K Appel","year":"1976","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable. Bull. Amer. Math. Soc. 82(5), 711\u2013712 (1976)","journal-title":"Bull. Amer. Math. Soc."},{"key":"17_CR3","volume-title":"Graphs and Hypergraphs","author":"C Berge","year":"1976","unstructured":"Berge, C.: Graphs and Hypergraphs, revised edn. North-Holland Publishing Co., Amsterdam (1976)","edition":"revised"},{"key":"17_CR4","unstructured":"Bodlaender, H.L.: Open problems in parameterized and exact computation. Technical report UU-CS-2008-017, Utrecht University (2008)"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Proc. Camb. Philos. Soc. 37, 194\u2013197 (1941)","journal-title":"Proc. Camb. Philos. Soc."},{"issue":"4","key":"17_CR6","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67(4), 789\u2013807 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR7","unstructured":"Cranston, D.W., Rabern, L.: Planar graphs are 9\/2-colorable and have independence ratio at least 3\/13 (2015). \n                      http:\/\/arxiv.org\/abs\/1410.7233"},{"key":"17_CR8","unstructured":"Crowston, R., Fellows, M., Gutin, G., Jones, M., Rosamond, F., Thomass\u00e9, S., Yeo, A.: Simultaneously satisfying linear equations over \n                      \n                        \n                      \n                      $$\\mathbb{F}_2$$\n                      \n                        \n                          \n                            F\n                            2\n                          \n                        \n                      \n                    : MaxLin2 and Max-\n                      \n                        \n                      \n                      $$r$$\n                      \n                        \n                          r\n                        \n                      \n                    -Lin2 parameterized above average. In: Proceedings of FSTTCS 2011, pp. 229\u2013240 (2011)"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-642-31594-7_21","volume-title":"Automata, Languages, and Programming","author":"R Crowston","year":"2012","unstructured":"Crowston, R., Jones, M., Mnich, M.: Max-cut parameterized above the Edwards-Erd\u0151s bound. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 242\u2013253. Springer, Heidelberg (2012)"},{"key":"17_CR10","unstructured":"Cygan, M., Fomin, F., Jansen, B., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Open problems from the Bedlewo school on parameterized algorithms and complexity (2014). \n                      http:\/\/fptschool.mimuw.edu.pl\/opl.pdf"},{"key":"17_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015)"},{"issue":"1","key":"17_CR12","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/2462896.2462899","volume":"5","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On multiway cut parameterized above lower bounds. ACM Trans. Comput. Theory 5(1), 3:1\u20133:11 (2013)","journal-title":"ACM Trans. Comput. Theory"},{"key":"17_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/978-3-662-44777-2_29","volume-title":"Algorithms - ESA 2014","author":"Z Dvo\u0159\u00e1k","year":"2014","unstructured":"Dvo\u0159\u00e1k, Z., Mnich, M.: Large independent sets in triangle-free planar graphs. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 346\u2013357. Springer, Heidelberg (2014)"},{"issue":"3","key":"17_CR14","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1112\/jlms\/jdt085","volume":"89","author":"Z Dvo\u0159\u00e1k","year":"2014","unstructured":"Dvo\u0159\u00e1k, Z., Sereni, J.-S.S., Volec, J.: Subcubic triangle-free graphs have fractional chromatic number at most 14\/5. J. London Math. Soc. 89(3), 641\u2013662 (2014)","journal-title":"J. London Math. Soc."},{"issue":"3","key":"17_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"David Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 27 (electronic) (1999)","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"3","key":"17_CR16","doi-asserted-by":"publisher","first-page":"1458","DOI":"10.1137\/120870463","volume":"26","author":"L Faria","year":"2012","unstructured":"Faria, L., Klein, S., Stehl\u00edk, M.: Odd cycle transversals and independent sets in fullerene graphs. SIAM J. Discrete Math. 26(3), 1458\u20131469 (2012)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"17_CR17","first-page":"26","volume":"2","author":"MR Fellows","year":"2012","unstructured":"Fellows, M.R., Guo, J., Marx, D., Saurabh, S.: Data reduction and problem kernels (Dagstuhl Seminar 12241). Dagstuhl Reports 2(6), 26\u201350 (2012)","journal-title":"Dagstuhl Reports"},{"issue":"20","key":"17_CR18","doi-asserted-by":"publisher","first-page":"2742","DOI":"10.1016\/j.disc.2010.05.028","volume":"310","author":"H Fleischner","year":"2010","unstructured":"Fleischner, H., Sabidussi, G., Sarvanov, V.I.: Maximum independent sets in 3- and 4-regular Hamiltonian graphs. Discrete Math. 310(20), 2742\u20132749 (2010)","journal-title":"Discrete Math."},{"key":"17_CR19","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, New York (1979)"},{"key":"17_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-642-29344-3_35","volume-title":"LATIN 2012: Theoretical Informatics","author":"AC Giannopoulou","year":"2012","unstructured":"Giannopoulou, A.C., Kolay, S., Saurabh, S.: New lower bound on Max Cut of hypergraphs with an application to r-Set Splitting. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 408\u2013419. Springer, Heidelberg (2012)"},{"issue":"4","key":"17_CR21","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M Grohe","year":"2003","unstructured":"Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23(4), 613\u2013632 (2003)","journal-title":"Combinatorica"},{"key":"17_CR22","unstructured":"Gr\u00f6tzsch, H.: Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz f\u00fcr dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe, 8, 109\u2013120 (1958\/1959)"},{"issue":"41","key":"17_CR23","doi-asserted-by":"publisher","first-page":"5744","DOI":"10.1016\/j.tcs.2011.06.018","volume":"412","author":"G Gutin","year":"2011","unstructured":"Gutin, G., Jones, M., Yeo, A.: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. Theoret. Comput. Sci. 412(41), 5744\u20135751 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"8","key":"17_CR24","doi-asserted-by":"publisher","first-page":"872","DOI":"10.1016\/j.jcss.2010.05.001","volume":"76","author":"G Gutin","year":"2010","unstructured":"Gutin, G., Kim, E.J., Mnich, M., Yeo, A.: Betweenness parameterized above tight lower bound. J. Comput. System Sci. 76(8), 872\u2013878 (2010)","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"17_CR25","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.jcss.2011.01.004","volume":"78","author":"G Gutin","year":"2012","unstructured":"Gutin, G., van Iersel, L., Mnich, M., Yeo, A.: Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables. J. Comput. System Sci. 78(1), 151\u2013163 (2012)","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"17_CR26","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/j.jctb.2005.07.009","volume":"96","author":"CC Heckman","year":"2006","unstructured":"Heckman, C.C., Thomas, R.: Independent sets in triangle-free cubic planar graphs. J. Combin. Theory Ser. B 96(2), 253\u2013275 (2006)","journal-title":"J. Combin. Theory Ser. B"},{"key":"17_CR27","doi-asserted-by":"crossref","unstructured":"Kammer, F., Tholey, T.: Approximate tree decompositions of planar graphs in linear time. In: Proceedings of SODA 2012, pp. 683\u2013698 (2012)","DOI":"10.1137\/1.9781611973099.57"},{"issue":"2","key":"17_CR28","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1137\/110827879","volume":"26","author":"AD King","year":"2012","unstructured":"King, A.D., Lu, L., Peng, X.: A fractional analogue of Brooks\u2019 theorem. SIAM J. Discrete Math. 26(2), 452\u2013471 (2012)","journal-title":"SIAM J. Discrete Math."},{"issue":"24","key":"17_CR29","doi-asserted-by":"publisher","first-page":"3502","DOI":"10.1016\/j.disc.2012.07.039","volume":"312","author":"L Lu","year":"2012","unstructured":"Lu, L., Peng, X.: The fractional chromatic number of triangle-free graphs with \n                      \n                        \n                      \n                      $$\\Delta \\le 3$$\n                      \n                        \n                          \n                            \u0394\n                            \u2264\n                            3\n                          \n                        \n                      \n                    . Discrete Math. 312(24), 3502\u20133516 (2012)","journal-title":"Discrete Math."},{"issue":"2","key":"17_CR30","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"17_CR31","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. Comput. System Sci. 75(2), 137\u2013153 (2009)","journal-title":"J. Comput. System Sci."},{"key":"17_CR32","unstructured":"Mnich, M.: Algorithms in moderately exponential time. Ph.D. thesis, TU Eindhoven (2010)"},{"key":"17_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-642-34611-8_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Mnich","year":"2012","unstructured":"Mnich, M., Zenklusen, R.: Bisections above tight lower bounds. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 184\u2013193. Springer, Heidelberg (2012)"},{"key":"17_CR34","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04016-0","volume-title":"Graph Colouring and the Probabilistic Method","author":"M Molloy","year":"2002","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics, vol. 23. Springer, Berlin (2002)"},{"key":"17_CR35","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31. OUP, Oxford (2006)"},{"issue":"1","key":"17_CR36","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N Robertson","year":"1997","unstructured":"Robertson, N., Sanders, D., Seymour, P., Thomas, R.: The four-colour theorem. J. Combin. Theory Ser. B 70(1), 2\u201344 (1997)","journal-title":"J. Combin. Theory Ser. B"},{"key":"17_CR37","volume-title":"Fractional Graph Theory","author":"ER Scheinerman","year":"2011","unstructured":"Scheinerman, E.R., Ullman, D.H.: Fractional Graph Theory. Dover Publications Inc., Mineola (2011)"},{"key":"17_CR38","unstructured":"Sikdar, S.: Parameterizing from the extremes. Ph.D. thesis, The Institute of Mathematical Sciences, Chennai (2010)"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-30139-6_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T11:01:24Z","timestamp":1559386884000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-30139-6_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319301389","9783319301396"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-30139-6_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}