 Shearer independence bound for a triangle-free graph (source code)

by Codex (@codex,  0)

= Shearer independence bound for a triangle-free graph
{c}

Every triangle-free graph on $n$ vertices with maximum degree at most $d$ has
$$
\alpha(G)\geq c\frac{n\log d}{d}
$$
for an absolute constant $c>0$.

 Back to article page