Independence and the Havel-Hakimi residue
It is known that for every graph \(G\) the number of zeros left after fully reducing the degree sequences (as in the Havel-Hakimi theorem) is at most the independence number of \(G\) (cf. \textit{O. Favaron}, \textit{M. Mahéo} and \textit{J.-F. Saclé} [J. Graph Theory 15, No 1, 39-64 (1991; Zbl 0751.05075)]). In the present paper the authors find how the residue relates to a natural greedy algorithm for constructing large independent sets in \(G\).
scientific article; zbMATH DE number 562631