The independence number is the largest cardinality of an independent set in a graph. Since every colour class is independent,
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.