MSOL partitioning problems on graphs of bounded treewidth and clique-width

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 verte...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2007-05, Vol.377 (1), p.260-267
Main Author: Rao, Michaël
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Clique-width
Combinatorics
Combinatorics. Ordered structures
Computer Science
Computer science
control theory
systems
Data Structures and Algorithms
Discrete Mathematics
Exact sciences and technology
General logic
Graph algorithms
Graph theory
Logic and foundations
Logic in Computer Science
Mathematical logic, foundations, set theory
Mathematics
Monadic second order logic
Sciences and techniques of general use
Theoretical computing
Treewidth
Vertex partitioning
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2007.03.043