Universality in graph properties with degree restrictions
Izak Broere, Johannes Heidema, Peter Mihók · Discussiones Mathematicae Graph Theory · 2013
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 I c of all countable graphs (since every graph in I c is isomorphic to an induced subgraph of R).A brief overview of known universality results for some induced-hereditary subsets of 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 † Peter Mihók passed away on