Article ID Journal Published Year Pages File Type
436528 Theoretical Computer Science 2008 38 Pages PDF
Abstract

We consider the notion of modular decomposition for countable graphs. The modular decomposition of a graph given with an enumeration of its set of vertices can be defined by formulas of monadic second-order logic. Another result is the definition of a representation of modular decompositions by low degree relational structures. Such relational structures can also be defined in the considered graph by monadic second-order formulas.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics