| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 438596 | Theoretical Computer Science | 2007 | 8 Pages |
Abstract
We show that a class of vertex partitioning problems that can be expressed in monadic second order logic (MSOL) are polynomials on graphs of bounded clique-width. This class includes coloring, H-free coloring, domatic number and partition into perfect graphs. Moreover we show that a class of vertex and edge partitioning problems are polynomials on graphs of bounded treewidth.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
