Broere, Izak; Heidema, Johannes; Mihók, Peter Universality in graph properties with degree restrictions. (English) Zbl 1274.05334 Discuss. Math., Graph Theory 33, No. 3, 477-492 (2013). Summary: Rado constructed a (simple) denumerable graph \(R\) with the positive integers as vertex set with the following edges: For given \(m\) and \(n\) with \(m < n, m\) is adjacent to \(n\) if \(n\) has a 1 in the \(m\)’th position of its binary expansion. It is well known that \(R\) is a universal graph in the set \(\mathcal I_c\) of all countable graphs (since every graph in \(\mathcal I_c\) is isomorphic to an induced subgraph of \(R\)). A brief overview of known universality results for some induced-hereditary subsets of \(\mathcal I_c\) is provided. We then construct a \(k\)-degenerate graph which is universal for the induced-hereditary property of finite \(k\)-degenerate graphs. In order to attempt the corresponding problem for the property of countable graphs with colouring number at most \(k + 1\), the notion of a property with assignment is introduced and studied. Using this notion, we are able to construct a universal graph in this graph property and investigate its attributes. MSC: 05C63 Infinite graphs Keywords:countable graph; universal graph; induced-hereditary; \(k\)-degenerate graph; graph with colouring number at most \(k + 1\); graph property with assignment PDFBibTeX XMLCite \textit{I. Broere} et al., Discuss. Math., Graph Theory 33, No. 3, 477--492 (2013; Zbl 1274.05334) Full Text: DOI