Universal Graphs for Two Graph Properties

Abstract

The graphs we consider are all countable. A graph \(U\) is universal in a given set \(\mathcal{P}\) of graphs if every graph in \(\mathcal{P}\) is an induced subgraph of \(U\) and \(U \in \mathcal{P}\). In this paper we show the existence of a universal graph in the set of all countable graphs with block order bounded by a fixed positive integer. We also investigate some classes of interval graphs and work towards finding universal graphs for them. The sets of graphs we consider are all examples of induced-hereditary graph properties.