On variations of \(P_{4}\)-sparse graphs (Q1406046): Difference between revisions

A graph is \(P_4\)-sparse if every subgraph induced by five vertices contains at most one \(P_4\). Hoàng, who introduced this class, characterised \(P_4\)-sparse graphs by their prime graphs under modular decomposition. A \(P_4\)-extension is a graph on five vertices containing a \(P_4\). \(P_4\)-sparse graphs and several superclasses defined by forbidden \(P_4\)-extensions have bounded clique-width. This allows linear-time algorithms for all problems expressible in LinEMSOL(\(\tau_{1,\text{ L}}\)) when restricted to such a class, see \textit{B. Courcelle, J. A. Makowsky} and \textit{U. Rotics} [Theory Comput. Syst. 33, 125-150 (2000; Zbl 1009.68102)]. The authors classify all superclasses of \(P_4\)-sparse graphs defined by forbidding one \(P_4\)-extension into classes of bounded clique-width and classes of unbounded clique-width. A similar classification of classes defined by up to three forbidden \(P_4\)-extensions was given in a related paper additionally authored by \textit{F. F. Dragan} and \textit{H.-O. Le} [Lect. Notes Comput. Sci. 2573, 57-67 (2002; Zbl 1022.68090)].