{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T05:55:04Z","timestamp":1757310904410,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031433795"},{"type":"electronic","value":"9783031433801"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43380-1_9","type":"book-chapter","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:29:12Z","timestamp":1695414552000},"page":"116-129","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Cutting Barnette Graphs Perfectly is Hard"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0534-6417","authenticated-orcid":false,"given":"Dibyayan","family":"Chakraborty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julien","family":"Duron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"issue":"2","key":"9_CR1","first-page":"73","volume":"3","author":"T Akiyama","year":"1980","unstructured":"Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inf. Process. 3(2), 73\u201376 (1980)","journal-title":"J. Inf. Process."},{"issue":"2","key":"9_CR2","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/jgt.20390","volume":"62","author":"PS Bonsma","year":"2009","unstructured":"Bonsma, P.S.: The complexity of the matching-cut problem for planar graphs and other graph classes. J. Graph Theory 62(2), 109\u2013126 (2009)","journal-title":"J. Graph Theory"},{"key":"9_CR3","unstructured":"Bouquet, V., Picouleau, C.: The complexity of the perfect matching-cut problem. arXiv preprint arXiv:2011.03318 (2020)"},{"issue":"5","key":"9_CR4","doi-asserted-by":"publisher","first-page":"1238","DOI":"10.1007\/s00453-020-00782-8","volume":"83","author":"C-Y Chen","year":"2021","unstructured":"Chen, C.-Y., Hsieh, S.-Y., Le, H.-O., Le, V.B., Peng, S.-L.: Matching cut in graphs with large minimum degree. Algorithmica 83(5), 1238\u20131255 (2021)","journal-title":"Algorithmica"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/jgt.3190080106","volume":"8","author":"V Chv\u00e1tal","year":"1984","unstructured":"Chv\u00e1tal, V.: Recognizing decomposable graphs. J. Graph Theory 8(1), 51\u201353 (1984)","journal-title":"J. Graph Theory"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2020.02.010","volume":"815","author":"A Darmann","year":"2020","unstructured":"Darmann, A., D\u00f6cker, J.: On a simple hard variant of not-all-equal 3-SAT. Theor. Comput. Sci. 815, 147\u2013152 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9_CR7","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1016\/j.dam.2008.06.013","volume":"157","author":"D De Werra","year":"2009","unstructured":"De Werra, D., Demange, M., Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring on planar, bipartite and split graphs: complexity and approximation. Discret. Appl. Math. 157(4), 819\u2013832 (2009)","journal-title":"Discret. Appl. Math."},{"issue":"17","key":"9_CR8","doi-asserted-by":"publisher","first-page":"3552","DOI":"10.1016\/j.dam.2009.02.009","volume":"157","author":"N Derhy","year":"2009","unstructured":"Derhy, N., Picouleau, C.: Finding induced trees. Discret. Appl. Math. 157(17), 3552\u20133557 (2009)","journal-title":"Discret. Appl. Math."},{"key":"9_CR9","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)","edition":"4"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Chakraborty, D., Duron, J.: Cutting Barnette graphs perfectly is hard. arXiv:2302.11667 (2023)","DOI":"10.1007\/978-3-031-43380-1_9"},{"key":"9_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103210","volume":"91","author":"T Feder","year":"2021","unstructured":"Feder, T., Hell, P., Subi, C.S.: Distance-two colourings of Barnette graphs. Eur. J. Comb. 91, 103210 (2021)","journal-title":"Eur. J. Comb."},{"key":"9_CR12","unstructured":"Feder, T., Subi, C.S.: On Barnette\u2019s conjecture. Electron. Colloquium Comput. Complex. TR06-015 (2006)"},{"key":"9_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2022.106294","volume":"179","author":"C Feghali","year":"2023","unstructured":"Feghali, C.: A note on matching-cut in P$${}_{\\text{ t }}$$-free graphs. Inf. Process. Lett. 179, 106294 (2023)","journal-title":"Inf. Process. Lett."},{"key":"9_CR14","unstructured":"Feghali, C., Lucke, F., Paulusma, D., Ries, B.: New hardness results for (perfect) matching cut and disconnected perfect matching. CoRR, abs\/2212.12317 (2022)"},{"key":"9_CR15","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jcss.2021.07.005","volume":"123","author":"PA Golovach","year":"2022","unstructured":"Golovach, P.A., Komusiewicz, C., Kratsch, D., Le, V.B.: Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. J. Comput. Syst. Sci. 123, 76\u2013102 (2022)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9_CR17","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9_CR18","first-page":"128","volume":"5","author":"P Heggernes","year":"1998","unstructured":"Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nord. J. Comput. 5(2), 128\u2013142 (1998)","journal-title":"Nord. J. Comput."},{"key":"9_CR19","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations. The IBM Research Symposia Series, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, 20\u201322 March 1972, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"9_CR20","unstructured":"Kasteleyn, P.: Graph theory and crystal physics. Graph Theory Theor. Phys. 43\u2013110 (1967)"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.dam.2019.12.010","volume":"283","author":"C Komusiewicz","year":"2020","unstructured":"Komusiewicz, C., Kratsch, D., Le, V.B.: Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms. Discret. Appl. Math 283, 44\u201358 (2020)","journal-title":"Discret. Appl. Math"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Korobitsin, D.V.: On the complexity of domination number determination in monogenic classes of graphs (1992)","DOI":"10.1515\/dma.1992.2.2.191"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1007\/11752578_121","volume-title":"Parallel Processing and Applied Mathematics","author":"A Kosowski","year":"2006","unstructured":"Kosowski, A., Ma\u0142afiejski, M., \u017byli\u0144ski, P.: Parallel processing subsystems with redundancy in\u00a0a\u00a0distributed environment. In: Wyrzykowski, R., Dongarra, J., Meyer, N., Wa\u015bniewski, J. (eds.) PPAM 2005. LNCS, vol. 3911, pp. 1002\u20131009. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11752578_121"},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/j.tcs.2015.10.016","volume":"609","author":"D Kratsch","year":"2016","unstructured":"Kratsch, D., Le, V.B.: Algorithms solving the matching cut problem. Theor. Comput. Sci. 609, 328\u2013335 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2018.10.029","volume":"770","author":"H-O Le","year":"2019","unstructured":"Le, H.-O., Le, V.B.: A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter. Theor. Comput. Sci. 770, 69\u201378 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR26","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2022.07.035","volume":"931","author":"VB Le","year":"2022","unstructured":"Le, V.B., Telle, J.A.: The perfect matching cut problem revisited. Theor. Comput. Sci. 931, 117\u2013130 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Loverov, Ya.A., Orlovich, Y.L.: NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs. J. Appl. Ind. Math. 14, 353\u2013368 (2020)","DOI":"10.1134\/S1990478920020131"},{"key":"9_CR28","unstructured":"Lucke, F., Paulusma, D., Ries, B.: Finding matching cuts in H-free graphs. In: Bae, S.W., Park, H. (eds.) 33rd International Symposium on Algorithms and Computation, ISAAC 2022. LIPIcs, Seoul, Korea, 19\u201321 December 2022, vol. 248, pp. 22:1\u201322:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"9_CR29","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.tcs.2022.09.014","volume":"936","author":"F Lucke","year":"2022","unstructured":"Lucke, F., Paulusma, D., Ries, B.: On the complexity of matching cut for graphs of bounded radius and H-free graphs. Theor. Comput. Sci. 936, 33\u201342 (2022)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9_CR30","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/jgt.20085","volume":"49","author":"D Marx","year":"2005","unstructured":"Marx, D.: NP-completeness of list coloring and precoloring extension on the edges of planar graphs. J. Graph Theory 49(4), 313\u2013324 (2005)","journal-title":"J. Graph Theory"},{"key":"9_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2019.100553","volume":"35","author":"M Miotk","year":"2020","unstructured":"Miotk, M., Topp, J., \u017byli\u0144ski, P.: Disjoint dominating and 2-dominating sets in graphs. Discret. Optim. 35, 100553 (2020)","journal-title":"Discret. Optim."},{"issue":"2","key":"9_CR32","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/49097.49099","volume":"19","author":"BME Moret","year":"1988","unstructured":"Moret, B.M.E.: Planar NAE3SAT is in P. SIGACT News 19(2), 51\u201354 (1988)","journal-title":"SIGACT News"},{"issue":"5","key":"9_CR33","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1002\/jgt.3190130502","volume":"13","author":"AM Moshi","year":"1989","unstructured":"Moshi, A.M.: Matching cutsets in graphs. J. Graph Theory 13(5), 527\u2013536 (1989)","journal-title":"J. Graph Theory"},{"issue":"6","key":"9_CR34","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1016\/j.disc.2017.01.006","volume":"340","author":"A Munaro","year":"2017","unstructured":"Munaro, A.: On line graphs of subcubic triangle-free graphs. Discret. Math. 340(6), 1210\u20131226 (2017)","journal-title":"Discret. Math."},{"key":"9_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/3-540-45477-2_26","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Patrignani","year":"2001","unstructured":"Patrignani, M., Pizzonia, M.: The complexity of the matching-cut problem. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 284\u2013295. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45477-2_26"},{"issue":"1","key":"9_CR36","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"LJ Stockmeyer","year":"1982","unstructured":"Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15(1), 14\u201319 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"68","key":"9_CR37","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1080\/14786436108243366","volume":"6","author":"HNV Temperley","year":"1961","unstructured":"Temperley, H.N.V., Fisher, M.E.: Dimer problem in statistical mechanics-an exact result. Philos. Mag. 6(68), 1061\u20131063 (1961)","journal-title":"Philos. Mag."},{"issue":"2","key":"9_CR38","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"1","author":"WT Tutte","year":"1947","unstructured":"Tutte, W.T.: The factorization of linear graphs. J. Lond. Math. Soc. 1(2), 107\u2013111 (1947)","journal-title":"J. Lond. Math. Soc."},{"issue":"2","key":"9_CR39","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"SP Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2), 398\u2013427 (2001)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43380-1_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T11:58:13Z","timestamp":1703246293000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43380-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433795","9783031433801"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43380-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fribourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.unifr.ch\/wg2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}