Some Results on Elusive Graph Properties
Eberhard Triesch · SIAM Journal on Computing · 1994
This article proves several graph properties to be elusive. Two of the main results are l. If $\mathcal{P}$ is a decreasing graph property containing no graph of girth smaller than 5, then $\mathcal{P}$ is elusive. 2. The property of having matching number at most k, $k < \lfloor {{{|V|} / 2}} \rfloor $, is elusive. The proofs are all based on a topological method developed by Kahn, Saks, and Sturtevant.