Abstract
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, w e show that for every n ∈ N there is a unit interval graph I n and a permutation graph H n having n 2 vertices, each of whose clique—width is exactly n+1. These results allowus to see the borderwithin 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. N, n ≥ 3, has clique—width exactly n + 1.
Supported in part by postdoctoral fellowships at Bar-Ilan University and the University of Toronto.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
A. Brandstädt and F.F. Dragan. A linear-time algorithm for connected r-domination and steiner tree on distance-hereditary graphs. Networks, 31:177–182, 1998. 136
B. Courcelle, J. Engelfriet, and G. Rozenberg. Handle-rewriting hypergraph grammars. J. Comput. System Sci., 46:218–270, 1993. 135, 138
B. Courcelle, J.A. Makowsky, and U. Rotics. Linear time solvable optimization problems on certain structured graph families, extended abstract. Graph Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, volume 1517 of Lecture Notes in Computer Science, pages 1–16. Springer Verlang, 1998. 136
B. Courcelle, J.A. Makowsky, and U. Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic. To appear in Disc. Appl. Math. 136
B. Courcelle and S. Olariu. Upper bounds to the clique-width of graphs. to appear in Disc. Appl. Math. (http://dept-info.labri.u-bordeaux.fr/?courcell/ActSci.html), 1998. 135, 137, 138
A. D’Atri and M. Moscarini. Distance-hereditary graphs Steiner trees and connected domination. SIAM J. Comput., 17:521–538, 1988. 136
F.F. Dragan, F. Nicolai, and A. Brandstädt. LexBFS-orderings and powers of graphs. Graph Theoretic Concepts in Computer Science, 22th International Workshop, WG’96, volume 1197 of Lecture Notes in Computer Science, pages 166–180, 1997. 136
F.F. Dragan. Dominating cliques in distance-hereditary graphs. Algorithm theory-SWAT’94, volume 824 of Lecture Notes in Computer Science, pages 370–381, 1994. 136
M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980. 137, 143
P. L. Hammer and F. Maffray. Completely separable graphs. Disc. Appl. Math., 27:85–99, 1990. 136, 139
E. Howorka. A characterization of distance-hereditary graphs. Q. J. Math. Oxford Ser. (2), 28:417–420, 1977. 136
J.A. Makowsky and U. Rotics. On the classes of graphs with few P4’s. To appear in the International Journal of Foundations of Computer Science (IJFCS), 1999. 137
U. N. Peled and J. Wu. Restricted unimodular chordal graphs. To appear in Journal of Graph Theory, 1999. 136
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Golumbic, M.C., Rotics, U. (1999). On the Clique—Width of Perfect Graph Classes. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds) Graph-Theoretic Concepts in Computer Science. WG 1999. Lecture Notes in Computer Science, vol 1665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46784-X_14
Download citation
DOI: https://doi.org/10.1007/3-540-46784-X_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66731-5
Online ISBN: 978-3-540-46784-7
eBook Packages: Springer Book Archive