2000/09/01 by Martin Charles Golumbic, Udi Rotics · 231 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs #Combinatorics #Mathematics #Discrete mathematics #Clique graph #Treewidth #Split graph #Vertex (graph theory) #Chordal graph #Block graph #Bounded function #Graph #Pathwidth #Line graph #Graph power #1-planar graph
paper · doi:10.1142/s0129054100000260
published in International Journal of Foundations of Computer Science 11(03), 423-443 (World Scientific)
openalex publication_date 2000/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Graphs of clique–width at most k were introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined by k-expressions based on graph operations which use k vertex labels. In this paper we study the clique–width of perfect graph classes. On one hand, we show that every distance–hereditary graph, has clique–width at most 3, and a 3–expression defining it can be obtained in linear time. On the other hand, we show that the classes of unit interval and permutation graphs are not of bounded clique–width. More precisely, we show that for every [Formula: see text] there is a unit interval graph I n and a permutation graph H n having n 2 vertices, each of whose clique–width is at least n. These results allow us to see the border within the hierarchy of perfect graphs between classes whose clique–width is bounded and classes whose clique–width is unbounded. Finally we show that every n×n square grid, [Formula: see text], n ≥ 3, has clique–width exactly n+1.