A weighted graph polynomial from chromatic invariants of knots

被引：67

作者：

Noble, SD

Welsh, DJA

机构：

[1] Brunel Univ, Dept Math & Stat, Uxbridge UX3 3PH, Middx, England

[2] Math Inst, Oxford OX1 3LB, England

来源：

ANNALES DE L INSTITUT FOURIER | 1999年 / 49卷 / 03期

关键词：

chromatic invariants; weighted graphs; graph polynomial;

D O I：

10.5802/aif.1706

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Motivated by the work of Chmutov, Duzhin and Lando on Vassiliev invariants, we define a polynomial on weighted graphs which contains as specialisations the weighted chromatic invariants but also contains many other classical invariants including the Tutte and matching polynomials. It also gives the symmetric function generalisation of the chromatic polynomial introduced by Stanley. We study its complexity and prove hardness results for very restricted classes of graphs.

引用

页码：1057 / +

页数：32