On the structure of (\(P_{5}\),\,gem)-free graphs

DOI10.1016/j.dam.2004.01.009zbMath1084.05048OpenAlexW1493930654MaRDI QIDQ1764802

Andreas Brandstädt, Dieter Kratsch

Publication date: 22 February 2005

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

Full work available at URL: https://doi.org/10.1016/j.dam.2004.01.009

zbMATH Keywords

Clique widthModular decompositionPrime graphsModules and homogeneous sets in graphs(\(P_5\), gem)-free graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (22)

List coloring in the absence of two subgraphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ Bounding clique-width via perfect graphs ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Coloring graphs with no induced five‐vertex path or gem ⋮ Algorithmic aspects of switch cographs ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ 2-clique-bond of stable set polyhedra ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ Stable set and clique polytopes of \((P_{5},\,\mathrm{gem})\)-free graphs ⋮ Solving some NP-complete problems using split decomposition ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS ⋮ On algorithms for (\(P_5\), gem)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complement reducible graphs
• Modular decomposition and transitive orientation
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Handle-rewriting hypergraph grammars
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The Complexity of the Partial Order Dimension Problem
• A Linear Recognition Algorithm for Cographs
• Some classes of perfectly orderable graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey

This page was built for publication: On the structure of (\(P_{5}\),\,gem)-free graphs