{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:56:44Z","timestamp":1787507804300,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["948057, 683080"],"award-info":[{"award-number":["948057, 683080"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533356","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T16:23:38Z","timestamp":1659630218000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Stable graphs of bounded twin-width"],"prefix":"10.1145","author":[{"given":"Jakub","family":"Gajarsk\u00fd","sequence":"first","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Szymon","family":"Toru\u0144czyk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.048"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_13"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093870870"},{"key":"e_1_3_2_1_4_1","volume-title":"On the Monadic Second-Order Transduction Hierarchy. Log. Methods Comput. Sci. 6, 2","author":"Blumensath Achim","year":"2010","unstructured":"Achim Blumensath and Bruno Courcelle . 2010. On the Monadic Second-Order Transduction Hierarchy. Log. Methods Comput. Sci. 6, 2 ( 2010 ). https:\/\/doi.org\/10.2168\/LMCS-6(2:2)2010 10.2168\/LMCS-6(2:2)2010 Achim Blumensath and Bruno Courcelle. 2010. On the Monadic Second-Order Transduction Hierarchy. Log. Methods Comput. Sci. 6, 2 (2010). https:\/\/doi.org\/10.2168\/LMCS-6(2:2)2010"},{"key":"e_1_3_2_1_5_1","volume-title":"Graphs of bounded cliquewidth are polynomially \u03c7-bounded. Advances in Combinatorics2020:8","author":"Bonamy Marthe","year":"2020","unstructured":"Marthe Bonamy and Micha\u0142 Pilipczuk . 2020. Graphs of bounded cliquewidth are polynomially \u03c7-bounded. Advances in Combinatorics2020:8 ( 2020 ). Marthe Bonamy and Micha\u0142 Pilipczuk. 2020. Graphs of bounded cliquewidth are polynomially \u03c7-bounded. Advances in Combinatorics2020:8 (2020)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.118"},{"key":"e_1_3_2_1_7_1","volume-title":"ICALP 2021(LIPIcs, Vol.\u00a0198)","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet , Colin Geniet , Eun\u00a0Jung Kim , St\u00e9phan Thomass\u00e9 , and R\u00e9mi Watrigant . 2021 b. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring . In ICALP 2021(LIPIcs, Vol.\u00a0198) . Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, 35:1\u201335:20. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2021.35 10.4230\/LIPIcs.ICALP.2021.35 \u00c9douard Bonnet, Colin Geniet, Eun\u00a0Jung Kim, St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. 2021b. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. In ICALP 2021(LIPIcs, Vol.\u00a0198). Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, 35:1\u201335:20. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.35"},{"key":"e_1_3_2_1_8_1","volume-title":"Pierre Simon, St\u00e9phan Thomass\u00e9, and Szymon Toru\u0144czyk.","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet , Ugo Giocanti , Patrice Ossona de Mendez , Pierre Simon, St\u00e9phan Thomass\u00e9, and Szymon Toru\u0144czyk. 2021 c. Twin-width IV: low complexity matrices. CoRR abs\/2102.03117(2021). arxiv:2102.03117https:\/\/arxiv.org\/abs\/2102.03117 \u00c9douard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, St\u00e9phan Thomass\u00e9, and Szymon Toru\u0144czyk. 2021c. Twin-width IV: low complexity matrices. CoRR abs\/2102.03117(2021). arxiv:2102.03117https:\/\/arxiv.org\/abs\/2102.03117"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00062"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_77"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_3_2_1_13_1","first-page":"91","article-title":"Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Comb. Theory","volume":"97","author":"Courcelle Bruno","year":"2007","unstructured":"Bruno Courcelle and Sang-il Oum. 2007 . Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Comb. Theory , Ser. B 97 , 1 (2007), 91 \u2013 126 . https:\/\/doi.org\/10.1016\/j.jctb.2006.04.003 10.1016\/j.jctb.2006.04.003 Bruno Courcelle and Sang-il Oum. 2007. Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Comb. Theory, Ser. B 97, 1 (2007), 91\u2013126. https:\/\/doi.org\/10.1016\/j.jctb.2006.04.003","journal-title":"Ser. B"},{"key":"e_1_3_2_1_14_1","unstructured":"Anuj Dawar and Abhisekh Sankaran. 2020. MSO Undecidability for some Hereditary Classes of Unbounded Clique-Width. CoRR abs\/2011.02894(2020). arxiv:2011.02894https:\/\/arxiv.org\/abs\/2011.02894  Anuj Dawar and Abhisekh Sankaran. 2020. MSO Undecidability for some Hereditary Classes of Unbounded Clique-Width. CoRR abs\/2011.02894(2020). arxiv:2011.02894https:\/\/arxiv.org\/abs\/2011.02894"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112746"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.10.004"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3383206"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382093"},{"key":"e_1_3_2_1_19_1","unstructured":"Jakub Gajarsk\u00fd Michal Pilipczuk and Szymon Torunczyk. 2021. Stable graphs of bounded twin-width. CoRR abs\/2107.03711(2021). arXiv:2107.03711https:\/\/arxiv.org\/abs\/2107.03711  Jakub Gajarsk\u00fd Michal Pilipczuk and Szymon Torunczyk. 2021. Stable graphs of bounded twin-width. CoRR abs\/2107.03711(2021). arXiv:2107.03711https:\/\/arxiv.org\/abs\/2107.03711"},{"key":"e_1_3_2_1_20_1","volume-title":"Shrub-depth: Capturing Height of Dense Graphs. Log. Methods Comput. Sci. 15, 1","author":"Ganian Robert","year":"2019","unstructured":"Robert Ganian , Petr Hlin\u011bn\u00fd , Jaroslav Ne\u0161et\u0159il , Jan Obdr\u017e\u00e1lek , and Patrice Ossona de Mendez . 2019 . Shrub-depth: Capturing Height of Dense Graphs. Log. Methods Comput. Sci. 15, 1 (2019). https:\/\/doi.org\/10.23638\/LMCS-15(1:7)2019 10.23638\/LMCS-15(1:7)2019 Robert Ganian, Petr Hlin\u011bn\u00fd, Jaroslav Ne\u0161et\u0159il, Jan Obdr\u017e\u00e1lek, and Patrice Ossona de Mendez. 2019. Shrub-depth: Capturing Height of Dense Graphs. Log. Methods Comput. Sci. 15, 1 (2019). https:\/\/doi.org\/10.23638\/LMCS-15(1:7)2019"},{"key":"e_1_3_2_1_21_1","volume-title":"Ser. B(2020)","author":"Geelen Jim","unstructured":"Jim Geelen , O-joung Kwon, Rose McCarty , and Paul Wollan . 2020. The Grid Theorem for vertex-minors. J. Comb. Theory , Ser. B(2020) . In press . Jim Geelen, O-joung Kwon, Rose McCarty, and Paul Wollan. 2020. The Grid Theorem for vertex-minors. J. Comb. Theory, Ser. B(2020). In press."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4064\/am-19-3-4-413-441"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.01.005"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_3_2_1_26_1","volume-title":"Vol.\u00a028","author":"Ne\u0161et\u0159il Jaroslav","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez . 2012. Sparsity \u2014 Graphs , Structures, and Algorithms. Algorithms and combinatorics , Vol.\u00a028 . Springer . Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity \u2014 Graphs, Structures, and Algorithms. Algorithms and combinatorics, Vol.\u00a028. Springer."},{"key":"e_1_3_2_1_27_1","volume-title":"SODA 2021","author":"Ne\u0161et\u0159il Jaroslav","year":"2021","unstructured":"Jaroslav Ne\u0161et\u0159il , Patrice Ossona de Mendez , Micha\u0142 Pilipczuk , Roman Rabinovich , and Sebastian Siebertz . 2021 a. Rankwidth meets stability . In SODA 2021 . SIAM, 2014\u20132033. Jaroslav Ne\u0161et\u0159il, Patrice Ossona de Mendez, Micha\u0142 Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. 2021a. Rankwidth meets stability. In SODA 2021. SIAM, 2014\u20132033."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103223"},{"key":"e_1_3_2_1_29_1","volume-title":"Patrice Ossona de Mendez, and Sebastian Siebertz","author":"Ne\u0161et\u0159il Jaroslav","year":"2020","unstructured":"Jaroslav Ne\u0161et\u0159il , Patrice Ossona de Mendez, and Sebastian Siebertz . 2020 . Structural properties of the first-order transduction quasiorder. CoRR abs\/2010.02607(2020). arxiv:2010.02607https:\/\/arxiv.org\/abs\/2010.02607 Jaroslav Ne\u0161et\u0159il, Patrice Ossona de Mendez, and Sebastian Siebertz. 2020. Structural properties of the first-order transduction quasiorder. CoRR abs\/2010.02607(2020). arxiv:2010.02607https:\/\/arxiv.org\/abs\/2010.02607"},{"key":"e_1_3_2_1_30_1","volume-title":"STACS 2021(LIPIcs, Vol.\u00a0187)","author":"de Mendez Patrice Ossona","year":"2021","unstructured":"Patrice Ossona de Mendez . 2021 . First-Order Transductions of Graphs (Invited Talk) . In STACS 2021(LIPIcs, Vol.\u00a0187) . Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, 2:1\u20132:7. https:\/\/doi.org\/10.4230\/LIPIcs.STACS. 2021.2 10.4230\/LIPIcs.STACS.2021.2 Patrice Ossona de Mendez. 2021. First-Order Transductions of Graphs (Invited Talk). In STACS 2021(LIPIcs, Vol.\u00a0187). Schloss Dagstuhl \u2014 Leibniz-Zentrum f\u00fcr Informatik, 2:1\u20132:7. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.2"},{"key":"#cr-split#-e_1_3_2_1_31_1.1","unstructured":"Michal Pilipczuk Patrice\u00a0Ossona de Mendez and Sebastian Siebertz. 2022. Transducing paths in graph classes with unbounded shrubdepth. CoRR abs\/2203.16900(2022). https:\/\/doi.org\/10.48550\/arXiv.2203.16900 arXiv:2203.16900 10.48550\/arXiv.2203.16900"},{"key":"#cr-split#-e_1_3_2_1_31_1.2","doi-asserted-by":"crossref","unstructured":"Michal Pilipczuk Patrice\u00a0Ossona de Mendez and Sebastian Siebertz. 2022. Transducing paths in graph classes with unbounded shrubdepth. CoRR abs\/2203.16900(2022). https:\/\/doi.org\/10.48550\/arXiv.2203.16900 arXiv:2203.16900","DOI":"10.1016\/j.ejc.2022.103660"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22601"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90054-P"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90047-L"}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Haifa Israel","acronym":"LICS '22","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"]},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533356","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533356","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T15:02:10Z","timestamp":1750172530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533356"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":37,"alternative-id":["10.1145\/3531130.3533356","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533356","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}