Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets (Q1197003)

[For Part II see ibid. 110, No. 1-3, 81-118 (1992; Zbl 0774.05064).] A graph \(G\) is perfect if for every vertex-induced subgraph \(H\) of \(G\), the largest clique size of \(H\) equals the chromatic number of \(H\). Berge has conjectured---the Strong Perfect Graph Conjecture---that a graph is perfect if and only if the graph and its complement contain no odd-length chordless circuits other than triangles. A (0,1) matrix is linear if it does not contain a 2-by-2 submatrix of all ones. This paper studies graphs whose vertex-clique incidence matrix is linear. Such graphs are characterized by the property that they contain no induced subgraph isomorphic to \(K_ 4-e\), a complete graph on 4 vertices with on edge removed. This paper presents a new matrix-based proof of the Strong Perfect Graph Conjecture for \((K_ 4-e)\)-free graphs.