Details

Autor(en) / Beteiligte

• Gurski, Frank
• Wanke, Egon
• Brandes, Ulrik
• Wagner, Dorothea

Titel

The Tree-Width of Clique-Width Bounded Graphs without Kn,n

Ist Teil von

• Graph-Theoretic Concepts in Computer Science, 2000, Vol.1928, p.196-205

Ort / Verlag

Germany: Springer Berlin / Heidelberg

Erscheinungsjahr

2000

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.