Journal
THEORETICAL COMPUTER SCIENCE
Volume 377, Issue 1-3, Pages 260-267Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2007.03.043
Keywords
graph algorithms; monadic second order logic; vertex partitioning; clique-width; treewidth
Categories
Ask authors/readers for more resources
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. (c) 2007 Elsevier B.V All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
