On semi-P_ 4-sparse graphs

DOI10.1016/S0012-365X(96)00177-XMaRDI QIDQ1356751zbMATH OpenOpenAlexFDO

Authors Jean-Luc Fouquet, Vassilis Giakoumakis

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

modular decompositioncliquecoloringstable setindecomposable graphslinear recognition algorithmsemi-\(P_ 4\)-sparse graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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)

Recommendations

• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• On extended P₄-reducible and extended P₄-sparse graphs

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4206028 (Why is no real title available?)
• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 3708283 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 3318560 (Why is no real title available?)
• A Fast Algorithm for the Decomposition of Graphs and Posets
• A Linear Recognition Algorithm for Cographs
• A tree representation for \(P_ 4\)-sparse graphs
• Clustering and domination in perfect graphs
• Complement reducible graphs
• Four classes of perfectly orderable graphs
• Graph derivatives
• Graphs with unique maximal clumpings
• Incremental modular decomposition
• On a property of the class of n-colorable graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• On the closure of triangle-free graphs under substitution
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• The complexity of comparability graph recognition and coloring
• Transitiv orientierbare Graphen
• Two-Processor Scheduling with Start-Times and Deadlines
• Weakly triangulated graphs
• \(P_ 4\)-trees and substitution decomposition

Cited in

(15)

• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Minimal classes of graphs of unbounded clique-width
• On the stable set problem in special \(P_{5}\)-free graphs
• Stability number in subclasses of \(P_5\)-free graphs
• Stability in \(P_5\)- and banner-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• On the minimum sum coloring of P₄-sparse graphs
• Independent domination in finitely defined classes of graphs
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Minimal separators in \(P_4\)-sparse graphs
• Neighborhood covering and independence on P₄-tidy graphs and tree-cographs
• Scattering number and modular decomposition
• Augmenting graphs for independent sets
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Counting spanning trees using modular decomposition

This page was built for publication: On semi-\(P_ 4\)-sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356751)