MSO undecidability for hereditary classes of unbounded clique-width

Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditar...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 2025-01, Vol.123, p.103700, Article 103700
Main Authors: Dawar, Anuj, Sankaran, Abhisekh
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c292t-c5912ae278f1f0704b5bd30509f3f464bc0cdc83689f9a566cac37ea35422423
container_end_page
container_issue
container_start_page 103700
container_title European journal of combinatorics
container_volume 123
creator Dawar, Anuj
Sankaran, Abhisekh
description Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them.
doi_str_mv 10.1016/j.ejc.2023.103700
format article
fullrecord <record><control><sourceid>elsevier_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1016_j_ejc_2023_103700</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0195669823000173</els_id><sourcerecordid>S0195669823000173</sourcerecordid><originalsourceid>FETCH-LOGICAL-c292t-c5912ae278f1f0704b5bd30509f3f464bc0cdc83689f9a566cac37ea35422423</originalsourceid><addsrcrecordid>eNp9j8tOwzAQRb0AifL4AHb5gZSxHTuxWKGKl1TUBd1bznisOioN2Cmof4-rsmY1mtE9o3sYu-Uw58D13TCnAecChCy7bAHO2Ay4UbXWprtglzkPAJwrKWds8fa-qvY7Txi96-M2TocqjKnaUCIfJ5cOFW5dzpSrMZRgPx7Dvhzj157qn-inzTU7D26b6eZvXrH10-N68VIvV8-vi4dljcKIqUZluHAk2i7wAC00veq9BAUmyNDopkdAj53UnQnGKa3RoWzJSdUI0Qh5xfjpLaYx50TBfqb4URpaDvYobgdbxO1R3J7EC3N_Yqj0-o6UbMZIOyxuiXCyfoz_0L9sIWKZ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>MSO undecidability for hereditary classes of unbounded clique-width</title><source>ScienceDirect Freedom Collection 2022-2024</source><creator>Dawar, Anuj ; Sankaran, Abhisekh</creator><creatorcontrib>Dawar, Anuj ; Sankaran, Abhisekh</creatorcontrib><description>Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them.</description><identifier>ISSN: 0195-6698</identifier><identifier>DOI: 10.1016/j.ejc.2023.103700</identifier><language>eng</language><publisher>Elsevier Ltd</publisher><ispartof>European journal of combinatorics, 2025-01, Vol.123, p.103700, Article 103700</ispartof><rights>2023 The Author(s)</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c292t-c5912ae278f1f0704b5bd30509f3f464bc0cdc83689f9a566cac37ea35422423</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Dawar, Anuj</creatorcontrib><creatorcontrib>Sankaran, Abhisekh</creatorcontrib><title>MSO undecidability for hereditary classes of unbounded clique-width</title><title>European journal of combinatorics</title><description>Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them.</description><issn>0195-6698</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2025</creationdate><recordtype>article</recordtype><recordid>eNp9j8tOwzAQRb0AifL4AHb5gZSxHTuxWKGKl1TUBd1bznisOioN2Cmof4-rsmY1mtE9o3sYu-Uw58D13TCnAecChCy7bAHO2Ay4UbXWprtglzkPAJwrKWds8fa-qvY7Txi96-M2TocqjKnaUCIfJ5cOFW5dzpSrMZRgPx7Dvhzj157qn-inzTU7D26b6eZvXrH10-N68VIvV8-vi4dljcKIqUZluHAk2i7wAC00veq9BAUmyNDopkdAj53UnQnGKa3RoWzJSdUI0Qh5xfjpLaYx50TBfqb4URpaDvYobgdbxO1R3J7EC3N_Yqj0-o6UbMZIOyxuiXCyfoz_0L9sIWKZ</recordid><startdate>20250101</startdate><enddate>20250101</enddate><creator>Dawar, Anuj</creator><creator>Sankaran, Abhisekh</creator><general>Elsevier Ltd</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20250101</creationdate><title>MSO undecidability for hereditary classes of unbounded clique-width</title><author>Dawar, Anuj ; Sankaran, Abhisekh</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c292t-c5912ae278f1f0704b5bd30509f3f464bc0cdc83689f9a566cac37ea35422423</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2025</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Dawar, Anuj</creatorcontrib><creatorcontrib>Sankaran, Abhisekh</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><jtitle>European journal of combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Dawar, Anuj</au><au>Sankaran, Abhisekh</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>MSO undecidability for hereditary classes of unbounded clique-width</atitle><jtitle>European journal of combinatorics</jtitle><date>2025-01-01</date><risdate>2025</risdate><volume>123</volume><spage>103700</spage><pages>103700-</pages><artnum>103700</artnum><issn>0195-6698</issn><abstract>Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them.</abstract><pub>Elsevier Ltd</pub><doi>10.1016/j.ejc.2023.103700</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0195-6698
ispartof European journal of combinatorics, 2025-01, Vol.123, p.103700, Article 103700
issn 0195-6698
language eng
recordid cdi_crossref_primary_10_1016_j_ejc_2023_103700
source ScienceDirect Freedom Collection 2022-2024
title MSO undecidability for hereditary classes of unbounded clique-width
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T19%3A47%3A24IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-elsevier_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=MSO%20undecidability%20for%20hereditary%20classes%20of%20unbounded%20clique-width&rft.jtitle=European%20journal%20of%20combinatorics&rft.au=Dawar,%20Anuj&rft.date=2025-01-01&rft.volume=123&rft.spage=103700&rft.pages=103700-&rft.artnum=103700&rft.issn=0195-6698&rft_id=info:doi/10.1016/j.ejc.2023.103700&rft_dat=%3Celsevier_cross%3ES0195669823000173%3C/elsevier_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c292t-c5912ae278f1f0704b5bd30509f3f464bc0cdc83689f9a566cac37ea35422423%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true