2009/01/01 by Michael R. Fellows, Frances Rosamond, Udi Rotics +1 · 115 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Labeling and Dimension Problems #Combinatorics #Mathematics #Split graph #Discrete mathematics #Clique graph #Clique-width #Perfect graph #Vertex (graph theory) #Bounded function #Treewidth #Time complexity #Graph #Block graph #Clique #Chordal graph #Pathwidth #Line graph #Graph power #1-planar graph #Voltage graph
paper · doi:10.1137/070687256
published in SIAM Journal on Discrete Mathematics 23(2), 909-939 (Society for Industrial and Applied Mathematics)
openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in monadic second-order logic with second-order quantification on vertex sets, which includes NP-hard problems such as 3-colorability) can be solved in polynomial time for graphs of bounded clique-width. We show that the clique-width of a given graph cannot be absolutely approximated in polynomial time unless P = NP. We also show that, given a graph G and an integer k, deciding whether the clique-width of G is at most k is NP-complete. This solves a problem that has been open since the introduction of clique-width in the early 1990s.