Description of the Triangle-free Prime Graphs Having at Most Two Non Critical Vertices.

In a graph G = (V, E), a module is a vertex subset M such that every vertex outside M is adjacent to all or none of M. For example, ϕ, {x} (x∊ V) and V are modules of G, called trivial modules. A graph, all the modules of which are trivial, is prime; otherwise, it is decomposable. A vertex x of a prime graph G is critical if G - x is decomposable. We generalize this definition. A prime graph G = (V, E) is Xcritical, where X is a subset of V, if for each x ∊ X, x is a critical vertex. Moreover, G is (-k)-critical, where 0 = k = |V|, if G is (V\X)-critical for some subset X of V such that |X| = k. In 1993, J.H. Schmerl and W.T. Trotter characterized the V-critical graphs, called critical graphs with vertex set V. Recently, H. Belkhechine, I. Boudabbous and M.B. Elayech characterized the (-1)-critical graphs. In this paper, we characterize the (-k)-critical graphs within the family of triangle-free graphs where k = 2. [ABSTRACT FROM AUTHOR]