Independent sets of graphs

Abstract

A set I of vertices of a graph G is called an independent set of G if no edge of G is a subset of I. The independence number of G is the size of a largest independent set of G and is denoted by α(G). The study of independent sets is a fundamental and widely-studied area of graph theory. We record several central results in the literature, and we include proofs of some of them with the aim of highlighting key ideas. The main focus is on bounds for α(G) and relations it has with other parameters of G. The performance of the bounds is investigated and some of their theoretical implications in different areas of study are discussed. Additionally, some approaches to solving the problem of finding a largest independent set of a graph are studied.