The monadic second-order logic of graphs XIV: uniformly sparse graphs and edge set quantifications
✍ Scribed by Bruno Courcelle
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 342 KB
- Volume
- 299
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
We consider the class US k of uniformly k-sparse simple graphs, i.e., the class of ÿnite or countable simple graphs, every ÿnite subgraph of which has a number of edges bounded by k times the number of vertices. We prove that for each k, every monadic second-order formula (intended to express a graph property) that uses variables denoting sets of edges can be e ectively translated into a monadic second-order formula where all set variables denote sets of vertices and that expresses the same property of the graphs in US k . This result extends to the class of uniformly k-sparse simple hypergraphs of rank at most m (for any k and m).
It follows that every subclass of US k consisting of ÿnite graphs of bounded clique-width has bounded tree-width. Clique-width is a graph complexity measure similar to tree-width and relevant to the construction of polynomial algorithms for NP-complete problems on special classes of graphs.