On variations of \(P_{4}\)-sparse graphs

DOI10.1016/S0166-218X(03)00180-XzbMath1022.05069MaRDI QIDQ1406046

Raffaele Mosca, Andreas Brandstädt

Publication date: 9 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

monadic second-order logiclinear time algorithmclique-widthprime graph\(P_4\)-extension\(P_4\)-spares graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items (12)

Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ On quasi-monotonous graphs ⋮ Bounding clique-width via perfect graphs ⋮ Classifying the clique-width of \(H\)-free bipartite 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 ⋮ The stable set polytope for some extensions of \(P_4\)-free graphs ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Bounding the clique-width of \(H\)-free split graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Modular decomposition and transitive orientation
• On the \(p\)-connectedness of graphs---a survey
• A nice class for the vertex packing problem
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Stability number of bull- and chair-free graphs revisited
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• The Complexity of the Partial Order Dimension Problem
• A Linear Recognition Algorithm for Cographs
• Some classes of perfectly orderable graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Graph Classes: A Survey
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• Difference graphs

This page was built for publication: On variations of \(P_{4}\)-sparse graphs