On induced-universal graphs for the class of bounded-degree graphs
For a family F of graphs, a graph U is said to be F-induced-universal if every graph of F is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on it vertices with degree at most k. For k even, our induced-universal graph has O(n(k/2)) vertices and for k odd it has O(n([k/2]-1/k) log(2+2/k) n) vertices. This construction improves a result of Butler by a multiplicative constant factor for the even case and by almost a multiplicative n(1/k) factor for the odd case. We also construct induced-universal graphs for the class of oriented graphs with bounded incoming and outgoing degree, slightly improving another result of Butler. (c) 2008 Elsevier B.V. All rights reserved,
universal graph bounded degree edge partition homomorphism combinatorial problems