Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm +2

A graph $U$ is an induced universal graph for a family $F$ of graphs if every graph in $F$ is a vertex-induced subgraph of $U$. For the family of all undirected graphs on $n$ verti…