Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract) (Q2768335)

The authors consider the following graph partitioning problems: dominating set, coloring and list-\(q\)-coloring with costs (fixed \(q\)), both from the viewpoint of the vertices and the edges. They show that all these problems (except edge-coloring) can be solved in polynomial time on graphs with clique-width bounded by some constant \(k\), if the \(k\)-expression of the input graph is given. In particular, they give the first polynomial algorithms for the chromatic number, edge-dominating set and list-\(q\)-coloring with costs on these classes of graphs. Unfortunately, the problem of recognizing and constructing the \(k\)-expressions of graphs with clique-width at most \(k\) is open except the case \(k\leq 3\) which can be solved in time \(O(n^2 m)\).NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].