loading page

Computing the clique-width of Cactus graphs
  • J. Leonardo González-Ruiz
J. Leonardo González-Ruiz

Corresponding Author:[email protected]

Author Profile

Abstract

Similar to the tree-width (twd), the clique-width (cwd) is an invariant of graphs. One of the best known relations between tree-width and clique-width is that \(cwd(G)\leq 3\cdot 2^{twd(G)-1}\). The tree-width of Cactus graphs is 2, so the clique-width for those graphs is smaller or equal than 6. In this paper we show that the clique-width of Cactus graphs is smaller or equal to 4 and we present a polynomial time algorithm which computes the \(4\)-expression.