On vertex orderings and the stability number in triangle-free graphs (Q5937606)

Let \(G= G(V,E)\) be a simple and finite graph. A set \(S\) of pairwise non-adajcent vertices in \(G\) is called stable. \(S\) is a maximal stable set in \(G\), if \(G\) has no stable \(S'\) with \(S\subset S'\), and the cardinality of such an \(S\) is called the stability number \(\alpha(G)\) of \(G\). A maximal stable set of \(G\) can be got by applying a certain algorithm, called greedy algorithm, on a given ordering \(v_1,\dots, v_n\) of the vertices of \(G\). For this algorithm the vertices in the given order are to scan and \(v_i\) is to put in \(S\) only if no vertex \(v_j\) in \(S\) with \(j< i\) is adjacent to it. The cardinality of the stable set that arises in this way is denoted by \(\alpha(G; v_1,\dots, v_n)\). If \(\alpha(G)= \alpha(G; v_1,\dots, v_n)\) then the ordering \(v_1,\dots, v_n\) is called an \(\alpha\)-ordering and it is known that the determination of an \(\alpha\)-ordering of a graph \(G\) is NP-hard. \textit{N. V. R. Mahadev} and \textit{B. A. Reed} [J. Graph Theory 30, No. 2, 113-120 (1999; Zbl 0918.05086)] investigated two types of vertex orderings satisfying certain conditions (Property 1 and Property 2) and they characterized a class of graphs for which a maximum stable set can be computed in polynomial time. The author gives a partial answer to a further question of Mahadev and Reed and he gives a complete characterization of all triangle-free graphs that have Property 2 (for every induced subgraph \(H\) of \(G\), every ordering of the vertices of \(H\) that is of the above shortly indicated Type 2 is an \(\alpha\)-ordering) in terms of an infinite number of forbidden induced subgraphs; here a maximal stable set also can be computed in polynomial time. Three classes \({\mathfrak C}_1\), \({\mathfrak C}_2\) and \({\mathfrak C}_3\) of graphs which contain these forbidden induced subgraphs are defined. \({\mathfrak C}_1\cup {\mathfrak C}_2\cup{\mathfrak C}_3\) is denoted by \({\mathfrak C}\). The following main result is proved: A triangle-free graph \(G\) has Property 2 iff it contains no graph in \({\mathfrak C}\) as an induced subgraph (Theorem 1). The proof of this theorem is given by proving a more extensive structural result (Theorem 2) which implies Theorem 1.