For every sufficiently large , there is a triangle-free graph on vertices with . One construction samples : with positive probability it has fewer than triangles and no independent set of size . Delete one vertex from each triangle and then take an induced -vertex subgraph.
Articles by others on the same topic
There are currently no matching articles.