摘要 : 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, Mahadev and Reed (J. Graph... 展开 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, Mahadev and Reed (J. Graph Theory 30 (1999) 113) 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 by characterizing all triangle-free graphs for which vertex orderings satisfying a certain condition yield a maximum stable set in polynomial time. 收起