Timeline for Graph containing every n-vertex graph as an induced subgraph
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2012 at 10:20 | answer | added | Peter Hegarty | timeline score: 4 | |
| Apr 8, 2012 at 4:52 | history | edited | Tony Huynh |
added graph theory tag
|
|
| Apr 7, 2012 at 13:23 | comment | added | Chris Godsil | Vu has shown that there is a graph on $2^{n+2}$ vertices that contains all graphs on $n$ vertices as an induced subgraph. (Combinatorica 16 (1996), 295-299). I suspect that the answer to your question is not known. | |
| Apr 7, 2012 at 13:19 | comment | added | Tony Huynh | Chris Godsil's answer over at Mathunderflow shows that the size of a graph which contains each $n$-vertex graph as an induced subgraph is exponential in $n$. See math.stackexchange.com/questions/75209/… | |
| Apr 7, 2012 at 13:00 | history | asked | Peter Hegarty | CC BY-SA 3.0 |