World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Part 1 (Selected papers from: Workshop on Theoretical Aspects of Computer Science (WG 99) Ascona, Switzerland, June 1999 Guest Editors: Stephan Eidenbenz, Gabriele Neyer and Peter Widmayer)No Access


    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 there is a unit interval graph In and a permutation graph Hn having n2 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, , n ≥ 3, has clique–width exactly n+1.

    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science