Computing Graph Polynomials on Graphs of Bounded Clique-Width | Zendy

Johann A. Makowsky | Zendy; Udi Rotics | Zendy; Ilya Averbouch | Zendy; Benny Godlin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Computing Graph Polynomials on Graphs of Bounded Clique-Width

Author(s) -

Johann A. Makowsky,

Udi Rotics,

Ilya Averbouch,

Benny Godlin

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-48381-0

DOI - 10.1007/11917496_18

Subject(s) - chromatic polynomial , combinatorics , mathematics , discrete mathematics , alternating polynomial , graph , chordal graph , bounded function , polynomial , matrix polynomial , mathematical analysis

We discuss the complexity of computing various graph polynomials of graphs of fixed clique-width. We show that the chromatic polynomial, the matching polynomial and the two-variable interlace polynomial of a graph G of clique-width at most k with n vertices can be computed in time O(nf( k)), where f(k) ≤3 for the inerlace polynomial, f(k) ≤2k+1 for the matching polynomial and f(k) ≤3 2k+2 for the chromatic polynomial.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research