Clique-Width for 4-Vertex Forbidden Subgraphs

2006/01/25 by Andreas Brandstadt, Andreas Brandstädt, Joost Engelfriet +4 · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Clique #Clique graph #Clique-sum #Clique-width #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Partial k-tree #Pathwidth #Split graph #Treewidth #Vertex (graph theory) #Voltage graph

paper · doi:10.1007/s00224-005-1199-1

openalex publication_date 2006/01/25 · crossref created 2006/01/25 · crossref issued 2006/02/08 · crossref published 2006/02/08 · crossref published-online 2006/02/08 · crossref published-print 2006/07/01 · crossref deposited 2019/05/24 · openalex created_date 2025/10/10 · crossref indexed 2026/03/11 · openalex updated_date 2026/07/28

Citations

• On maximal independent sets of vertices in claw-free graphs
• Three-colourability and forbidden subgraphs. II: polynomial algorithms
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile
• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• New Graph Classes of Bounded Clique-Width
• The Complexity of the Partial Order Dimension Problem
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• Combinatorial Relations and Chromatic Graphs

Cited by

• Clique-Width is NP-Complete
• Clique-width [wikipedia]