Similar to the tree-width (twd), the clique-width (cwd) is an invariant of graphs. A well known relationship between tree-width and clique-width is that c w d ( G ) ≤ 3 ⋅ 2 t w d ( G ) − 1 . It is also known that tree-width of Cactus graphs is 2, therefore the clique-width for those graphs is smaller or equal than 6. In this paper, it is shown that the clique-width of Cactus graphs is smaller or equal to 4 and we present a polynomial time algorithm which computes exactly a 4-expression.
No takes yet. Share an insight, caveat, or question.
González-Ruíz et al. (2016) studied this question.