Predavatelj: Bert Hartnell (Saint Mary’s University, Halifax, Kanada)
A well-covered graph (introduced by M. D. Plummer in 1970) is one in which every maximal
independent set of vertices is a maximum. Whereas determining the independence number of
an arbitrary graph is NP-complete, for a well-covered graph one can simply apply a greedy
algorithm. The problem of characterizing the well-covered graphs has not been so straight-
forward however. In this talk we will outline the approach taken to determine the well-covered
graphs that are planar triangulations (respectively, planar quadrangulations).
independent set of vertices is a maximum. Whereas determining the independence number of
an arbitrary graph is NP-complete, for a well-covered graph one can simply apply a greedy
algorithm. The problem of characterizing the well-covered graphs has not been so straight-
forward however. In this talk we will outline the approach taken to determine the well-covered
graphs that are planar triangulations (respectively, planar quadrangulations).