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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2007, 377, pp.260-267. 〈10.1016/j.tcs.2007.03.043〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00204064
Contributeur : Michael Rao <>
Soumis le : vendredi 11 janvier 2008 - 17:02:33
Dernière modification le : jeudi 15 novembre 2018 - 20:26:55

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

96