Monadic second-order definable graph orderings

DOI10.2168/LMCS-10(1:2)2014MaRDI QIDQ2871227zbMATH OpenFDO

Authors Achim Blumensath, Bruno Courcelle

Publication date 22 January 2014

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.8148

zbMATH Keywords

definabilitylinear ordersmonadic second-order logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Structural characterization of families of graphs (05C75) Formal languages and automata (68Q45)

Abstract: We study the question of whether, for a given class of finite graphs, one can define, for each graph of the class, a linear ordering in monadic second-order logic, possibly with the help of monadic parameters. We consider two variants of monadic second-order logic: one where we can only quantify over sets of vertices and one where we can also quantify over sets of edges. For several special cases, we present combinatorial characterisations of when such a linear ordering is definable. In some cases, for instance for graph classes that omit a fixed graph as a minor, the presented conditions are necessary and sufficient; in other cases, they are only necessary. Other graph classes we consider include complete bipartite graphs, split graphs, chordal graphs, and cographs. We prove that orderability is decidable for the so called HR-equational classes of graphs, which are described by equation systems and generalize the context-free languages.

Recommendations

• The monadic second-order logic of graphs. X: Linear orderings
• The monadic second-order logic of graphs. VIII: Orientations
• scientific article; zbMATH DE number 2079025
• The definition in monadic second-order logic of modular decompositions of ordered graphs
• Definability in first order theories of graph orderings

Cited in

(11)

• Tree-definable linear orders
• The monadic second-order logic of graphs. X: Linear orderings
• A monadic second-order definition of the structure of convex hypergraphs.
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• scientific article; zbMATH DE number 1114341 (Why is no real title available?)
• Order-theoretic Trees: Monadic Second-order Descriptions and Regularity
• Definability in first-order theories of graph orderings
• Definability in first order theories of graph orderings
• Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law
• Pathlength of outerplanar graphs
• Pathlength of outerplanar graphs

This page was built for publication: Monadic second-order definable graph orderings

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