文摘
The theory of simplicial graph decompositions studies the infinite graphs that are built from a sequence of irreducible graphs which are attached together at complete subgraphs. In this paper, we study the logical complexity of deciding if a graph is prime decomposable. A large part of this analysis involves determining which ordinals must appear in these types of decompositions.A result of Diestel says that every countable simplicial tree decomposition can be rearranged to have length at most ω. We show that no such ordinal bound can be found for the lengths of non-tree decompositions. More generally, we show that for each ordinal σ, there is a decomposable graph whose shortest simplicial decomposition has length exactly σ . Adapting this argument, we show that the index set of decomposable computable graphs DECOMPDECOMP is Π11 hard by showing that WOWO is 1-reducible to DECOMPDECOMP.