A multivariate interlace polynomial and its computation for graphs of bounded clique-width
type: Item
instance of: scholarly article
title: A multivariate interlace polynomial and its computation for graphs of bounded clique-width
zbMATH Open document ID: 1181.05010
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/117249
full work available at URL: v15i1r69.html
review text: Summary: We define a multivariate polynomial that generalizes in a unified way the two-variable interlace polynomial defined by Arratia, Bollobás and Sorkin on the one hand, and a one-variable variant of it defined by Aigner and van der Holst on the other. We determine a recursive definition for our polynomial that is based on local complementation and pivoting like the recursive definitions of Tutte's polynomial and of its multivariate generalizations are based on edge deletions and contractions. We also show that bounded portions of our polynomial can be evaluated in polynomial time for graphs of bounded clique-width. Our proof uses an expression of the interlace polynomial in monadic second-order logic, and works actually for every polynomial expressed in monadic second-order logic in a similar way.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 03C13
zbMATH DE Number: 5540974
MaRDI profile type: Publication
author: Bruno Courcelle
description: scientific article; zbMATH DE number 5540974