Polynomial-time recognition of clique-width ≤3 graphs

2011/05/10 by Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel +2 · 28 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Clique-sum #Clique-width #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph theory and applications #Line graph #Mathematics #Partial k-tree #Pathwidth #Treewidth

paper · pdf · doi:10.1016/j.dam.2011.03.020

published in Discrete Applied Mathematics 160(6), 834-865 (Elsevier BV)

openalex publication_date 2011/05/10 · crossref created 2011/05/10 · crossref issued 2012/04/01 · crossref published 2012/04/01 · crossref published-print 2012/04/01 · crossref deposited 2018/12/02 · openalex created_date 2025/10/10 · crossref indexed 2026/06/09 · openalex updated_date 2026/08/03

Citations

• NLC-2 Graph Recognition and Isomorphism
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Line graphs of bounded clique-width
• k-NLC graphs and polynomial algorithms
• New Graph Classes of Bounded Clique-Width
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• Approximating clique-width and branch-width

Cited by

• Clique-width [wikipedia]