On Vertex Orderings and the Stability Number in triangle-free Graphs

Abstract: Given an ordering of the vertices of a graph one can construct a maximal stable set of that graph applying a simple greedy algorithm. By investigating certain conditions on the orderings of the vertices, N.V.R. Mahadev and B.A. Reed [5] characterized a class of graphs for which a maximum stable set- and hence also the stability number- can be computed in polynomial time in this way. In this paper we give a partial answer to a question raised by them in [5] by characterizing all triangle-free graphs for which vertex orderings satisfying a certain condition yield a maximum stable set in polynomial time