On variations of P₄-sparse graphs
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)].
- On extended P₄-reducible and extended P₄-sparse graphs
- Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
- Linear time optimization algorithms for \(P_ 4\)-sparse graphs
- A tree representation for \(P_ 4\)-sparse graphs
- Recognizing P₄ -Sparse Graphs in Linear Time
- A Linear Recognition Algorithm for Cographs
- A nice class for the vertex packing problem
- A tree representation for \(P_ 4\)-sparse graphs
- Complement reducible graphs
- Difference graphs
- Efficient and practical algorithms for sequential modular decomposition
- Graph Classes: A Survey
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 3896983 (Why is no real title available?)
- scientific article; zbMATH DE number 1375569 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 1262783 (Why is no real title available?)
- scientific article; zbMATH DE number 1456953 (Why is no real title available?)
- Linear time optimization algorithms for \(P_ 4\)-sparse graphs
- Modular decomposition and transitive orientation
- On extended P₄-reducible and extended P₄-sparse graphs
- On the \(p\)-connectedness of graphs---a survey
- On the clique-width of graph with few \(P_{4}\)'s
- Recognizing P₄ -Sparse Graphs in Linear Time
- Some classes of perfectly orderable graphs
- Stability number of bull- and chair-free graphs revisited
- The Complexity of the Partial Order Dimension Problem
- Upper bounds to the clique width of graphs
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Linear time optimization algorithms for \(P_ 4\)-sparse graphs
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- Bounding clique-width via perfect graphs
- Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs
- Bounding clique-width via perfect graphs
- Clique-width of graph classes defined by two forbidden induced subgraphs
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- scientific article; zbMATH DE number 2096434 (Why is no real title available?)
- Bounding the clique-width of \(H\)-free split graphs
- Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
- On the minimum sum coloring of P₄-sparse graphs
- Minimal separators in \(P_4\)-sparse graphs
- On quasi-monotonous graphs
- Classifying the clique-width of \(H\)-free bipartite graphs
- The stable set polytope for some extensions of \(P_4\)-free graphs
This page was built for publication: On variations of \(P_{4}\)-sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1406046)
