I am looking for the tightest upper bound for the size of a maximum independent set in a general graph about which I know the size of nodes, edges, and the adjacency list. The only link I could find is Upper bound on the size of the maximum independent set, however I was wondering if someone can point out a better source or potentially a tighter bound for me. or where should I do my research for this?
Best known upper bound for the size of the maximum independent set in a given graph
graph theoryupper-lower-bounds
Best Answer
As in the accepted answer for the linked question, write $k$ for the maximum size of an independent set. The given bound is $$k\leq\frac12\left(1+\sqrt{1-8m-4n+4n^2}\right)=\frac12\left(1+\sqrt{(2n-1)^2-8m}\right)$$ or $$(2k-1)^2\leq(2n-1)^2-8m$$ In a triangle, we have $n=m=3,\ k=1$ and the bound is tight.