MSOL partitioning problems on graphs of bounded treewidth and clique-width - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Theoretical Computer Science Year : 2007

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.

Dates and versions

lirmm-00204064 , version 1 (11-01-2008)

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More