Abstract
We proof that every graph of clique-width k which does not contain the complete bipartite graph Kn,n for some n > 1 as a subgraph has tree-width at most 3k(n - 1) - 1. This immediately implies that a set of graphs of bounded clique-width has bounded tree-width if it is uniformly l-sparse, closed under subgraphs, of bounded degree, or planar.
The work of the first author was supported by the German Research Association (DFG) grant WA 674/9-1.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12308–340, 1991.
H.L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209:1–45, 1998.
B.D.G. Corneil, M. Habib, J.M. Lanlignel, B. Reed, and U. Rotics. Polynomial time recognition of clique-width at most three graphs. In Proceedings of Latin American Symposium on Theoretical Informatics (LATIN’ 2000), volume 1776 of LNCS. Springer-Verlag, 2000.
B. Courcelle, J.A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique width, extended abstract. In Proceedings of Graph-Theoretical Concepts in Computer Science, volume 1517 of LNCS, pages 1–16. Springer-Verlag, 1998.
B. Courcelle and S. Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101:77–114, 2000.
B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation, 85:12–75, 1990.
B. Courcelle. The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications. submitted for publication, 2000.
D.G. Corneil, Y. Perl, and L.K. Stewart. A linear recognition algorithm for cographs. SIAM Journal on Computing, 14(4):926–934, 1985.
M.C. Golumbic and U. Rotics. On the clique-width of perfect graph classes. In Proceedings of Graph-Theoretical Concepts in Computer Science, volume 1665 of LNCS, pages 135–147. Springer-Verlag, 1999.
F. Gurski. Algorithmische Charakterisierungen spezieller Graphklassen. Diplomarbeit, Heinrich-Heine-Universität, Düsseldorf, Germany, 1998.
Ö. Johansson. Clique-decomposition, NLC-decomposition, and modular decomposition-relationships and results for random graphs. Congressus Numerantium, 132:39–60, 1998.
Ö. Johansson. NLC2 decomposition in polynomial time. In Proceedings of GraphTheoretical Concepts in Computer Science, volume 1665 of LNCS, pages 110–121.Springer-Verlag, 1999.
N. Robertson and P.D. Seymour. Graph minors II. Algorithmic aspects of tree width. Journal of Algorithms, 7:309–322, 1986.
E. Wanke. k-NLC graphs and polynomial algorithms. Discrete Applied Mathematics, 54:251–266, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gurski, F., Wanke, E. (2000). The Tree-Width of Clique-Width Bounded Graphs without Kn,n . In: Brandes, U., Wagner, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2000. Lecture Notes in Computer Science, vol 1928. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40064-8_19
Download citation
DOI: https://doi.org/10.1007/3-540-40064-8_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41183-3
Online ISBN: 978-3-540-40064-6
eBook Packages: Springer Book Archive