Graphs with a small number of distinct induced subgraphs (Q1823262)

Let G be a finite, simple and undirected graph and i(G) denotes the total number of isomorphism types of induced subgraphs of G. An induced subgraph of G is called trivial if it is either complete or independent and let t(G) denote the maximum number of vertices of such a trivial subgraph of G. By Hajnal the conjecture is formulated that if G is a graph on n vertices and \(i(G)=o(n^ 2)\), then \(t(G)=n-o(n)\) holds. The proof of this conjecture is the main result of the present paper (Theorem 1.1). This proof is a very lengthy one and requires two steps which consist of results on graphs with large trivial subgraphs and on graphs without large trivial subgraphs; the second step is the more difficult and the more important one regarding to Theorem 1.1. For \(i(G)\leq \epsilon n^ 2\) and \(t(G)\geq (n-\epsilon^*)\cdot n\) are given the two estimations \(\epsilon <10^{-21}\) and \(\epsilon^*=4\epsilon\) which are not optimal values and which can be improved. The conjecture was also proved in a stronger form by Erdős and Hajnal. Finally this paper contains some interesting unsolved problems.