Universal graphs with a forbidden subtree

by Cherlin and Shelah. [ChSh:850]
J Combinatorial Theory. Ser. B, 2007
We show that the problem of the existence of universal graphs with specified forbidden subgraphs can be systematically reduced to certain critical cases by a simple pruning technique which simplifies the underlying structure of the forbidden graphs, viewed as trees of blocks. As an application, we characterize the trees T for which a universal countable T-free graph exists.

Back to the list of publications