Several notions of rank-width for countable graphs

DOI10.1016/J.JCTB.2016.12.002MaRDI QIDQ505916zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 26 January 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2016.12.002

zbMATH Keywords

compactnesslinear rank-widthrank-widthKoenig's lemma

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12) Enumeration in graph theory (05C30)

Recommendations

• Clique-width of countable graphs: a compactness property
• Clique-width of countable graphs: A compactness property.
• Algebraic and logical descriptions of generalized trees
• Rank-Width and Well-Quasi-Ordering
• Rank-width and vertex-minors

Cites work

• scientific article; zbMATH DE number 3805534 (Why is no real title available?)
• A model-theoretic characterisation of clique width
• Approximating clique-width and branch-width
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Clique-sums, tree-decompositions and compactness
• Clique-width of countable graphs: A compactness property.
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• Linear rank-width and linear clique-width of trees
• Rank-width and vertex-minors
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
• The rank-width of edge-coloured graphs
• Thread graphs, linear rank-width and their algorithmic applications

Cited in

(9)

• Induced betweenness in order-theoretic trees
• Clique-width of countable graphs: A compactness property.
• Regularity equals monadic second-order definability for quasi-trees
• Axiomatization of betweenness in order-theoretic trees
• Order-theoretic Trees: Monadic Second-order Descriptions and Regularity
• Clique-width of countable graphs: a compactness property
• Betweenness of partial orders
• Betweenness in order-theoretic trees
• Algebraic and logical descriptions of generalized trees

This page was built for publication: Several notions of rank-width for countable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q505916)