Computing the Clique-Width on Series-Parallel Graphs

Marco Antonio López-Medina, J. Leonardo González-Ruiz, J. Raymundo Marcial-Romero, J. A. Hernández


The clique-width (cwd) is an invariant of graphs which, similar to other invariants like the tree-width (twd) establishes a parameter for the complexity of a problem. For example, several problems with bounded clique-width can be solved in polynomial time. There is a well known relation between tree-width and clique-width denoted as cwd(G) ≤ 3 · 2 twd(G)−1 . Serial-parallel graphs have tree-width of at most 2, so its clique–width is at most 6 according to the previous relation. In this paper, we improve the bound for this particular case, showing that the clique-width of series-parallel graphs is smaller or equal to 5.


Graph theory, clique-width, tree-width, complexity, series-parallel

Full Text: PDF