is , but the best known algorithm is .

Independence number and Ramsey theory

An independent set of vertices (where is the floor function) in an n-vertex triangle-free graph is easy to find: either there is a vertex with at least neighbors (in which case those neighbors are an independent set) or all vertices have strictly less than neighbors (in which case any maximal independent set

1.Previous
3.Next