Characterizations for co-graphs defined by restricted NLC-width or clique-width operations

2006/01/18 by Frank Gurski · 16 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Clique #Clique-sum #Cograph #Combinatorics #Discrete mathematics #Graph #Graph theory and applications #Independent set #Indifference graph #Induced subgraph #Interconnection Networks and Systems #Line graph #Mathematics #Maximal independent set #Pathwidth #Split graph #Strong perfect graph theorem #Treewidth #Vertex (graph theory)

paper · pdf · doi:10.1016/j.disc.2005.11.014

published in Discrete Mathematics 306(2), 271-277 (Elsevier BV)

openalex publication_date 2006/01/18 · crossref created 2006/01/18 · crossref issued 2006/02/01 · crossref published 2006/02/01 · crossref published-print 2006/02/01 · crossref deposited 2020/04/12 · crossref indexed 2025/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Citations

• How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time
• Upper bounds to the clique width of graphs
• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• k-NLC graphs and polynomial algorithms
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• Approximating clique-width and branch-width
• Trivially perfect graphs
• Dacey Graphs

Cited by

• Trivially perfect graph [wikipedia]