The monadic second order logic of graphs. VI: On several representations of graphs by relational structures (Q1336623)

The paper continues the author's extensive study of graph properties expressible by formulas of monadic second order logic (MSOL). [For the previous five parts, cf. Zbl 0722.03008, Zbl 0694.68043, Zbl 0754.03006, Zbl 0731.03006, Zbl 0754.68065, respectively. Part VII is reviewed below.] The special interest in MSLO in this context is due to the fact that, while it is strong enough for expressing many important properties of graphs, it still has useful decidability properties; in particular, graph properties expressible in MSOL are decidable within sets generated by context-free graph grammars. In the usual representation of a graph as a logical structure, the domain consists of the vertices of the graph. The author notes that there are also alternative representations, and a central theme of this paper is the effect of the representation on the expressive power of MSOL. In particular, one may include also the edges in the domain and allow quantifications over them. It turns out that some new properties, like the existence of a Hamiltonian cycle, can be expressed by means of quantifications over edges and sets of edges. On the other hand, for any fixed \(k\), within the class of graphs of degree at most \(k\), edge quantifications do not increase the expressive power of MSOL. The same holds for the classes consisting of graphs which do not contain a given graph as a minor. Similar conclusions are arrived at for these classes with respect to the effect of allowing the use of orientations of edges. All graphs considered here are simple and loop- free. The paper contains also many other results concerning colorings, trees and planarity.