Skip to Main content Skip to Navigation
Journal articles

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

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.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00204064
Contributor : Michael Rao <>
Submitted on : Friday, January 11, 2008 - 5:02:33 PM
Last modification on : Friday, January 8, 2021 - 11:22:05 AM

Links full text

Identifiers

Collections

Citation

Michaël Rao. MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theoretical Computer Science, Elsevier, 2007, 377, pp.260-267. ⟨10.1016/j.tcs.2007.03.043⟩. ⟨lirmm-00204064⟩

Share

Metrics

Record views

296