On semi-P_ 4-sparse graphs

DOI10.1016/S0012-365X(96)00177-XzbMATH Open0873.05071OpenAlexW2576553421MaRDI QIDQ1356751FDOQ1356751

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

Recommendations

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

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)

Cites Work

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

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_4\)-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_4\)-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)