On semi-\(P_ 4\)-sparse graphs

DOI10.1016/S0012-365X(96)00177-XzbMath0873.05071OpenAlexW2576553421MaRDI QIDQ1356751

Vassilis Giakoumakis, Jean-Luc Fouquet

Publication date: 26 October 1997

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(96)00177-x

zbMATH Keywords

stable setcliquecoloringmodular decompositionindecomposable graphslinear recognition algorithmsemi-\(P_ 4\)-sparse graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Scattering number and modular decomposition, Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs, Independent domination in finitely defined classes of graphs, Counting spanning trees using modular decomposition, Minimal classes of graphs of unbounded clique-width, Stability number in subclasses of \(P_5\)-free graphs, Independent sets in extensions of 2\(K_{2}\)-free graphs, Augmenting graphs for independent sets, Stability in \(P_5\)- and banner-free graphs, On the stable set problem in special \(P_{5}\)-free graphs

Cites Work

• Weakly triangulated graphs
• On the closure of triangle-free graphs under substitution
• Clustering and domination in perfect graphs
• Graph derivatives
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• \(P_ 4\)-trees and substitution decomposition
• The complexity of comparability graph recognition and coloring
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On a property of the class of n-colorable graphs
• A Fast Algorithm for the Decomposition of Graphs and Posets
• A Linear Recognition Algorithm for Cographs
• Four classes of perfectly orderable graphs
• Incremental modular decomposition
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Two-Processor Scheduling with Start-Times and Deadlines
• Graphs with unique maximal clumpings
• Transitiv orientierbare Graphen
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item