Non-Ramsey graphs are \(c\log n\)-universal (Q1818220)

It is shown that all graphs that are non-Ramsey graphs are universal graphs. More specifically, it is shown that for any constant \(c_1 > 0\), there is a constant \(c_2 > 0\), such that if \(G\) is a graph on \(n\) vertices with neither \(G\) nor its complement \(\overline{G}\) containing a complete graph of order \(c_1 \log_2 n\), then \(G\) contains as induced subgraphs all graphs of order \(c_2 \log_2 n\).