Blumensath, Achim and Courcelle, Bruno - Monadic second-order definable graph orderings

lmcs:793 - Logical Methods in Computer Science, January 21, 2014, Volume 10, Issue 1 -
Monadic second-order definable graph orderings

Authors: Blumensath, Achim and Courcelle, Bruno

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.

Volume: Volume 10, Issue 1
Published on: January 21, 2014
Submitted on: December 9, 2011
Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic


Consultation statistics

This page has been seen 252 times.
This article's PDF has been downloaded 98 times.