Craig Larson

*Maximum Critical Independent Sets and Applications *

**Abstract**

A critical independence set of a graph is an independent set I , where |*I*|-|N(*I*)| ≥ |*J*|-|N(*J*)|, for any independent set *J*. Maximum critical independent sets can be found in polynomial-time. Examples, algorithms, and at least three applications will be discussed.

2) If a maximum critical independent set is a maximum independent set then the graph is a König-Egervary graph.

3) The neighbors of a maximum critical independent set are saturated by every maximum matching - that is, these sets are related to the matching structure of the graph.