Triangle-free graph with sub-power independence number
ID: triangle-free-graph-with-sub-power-independence-number
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.
New to topics? Read the docs here!