Voir la notice de l'article provenant de la source Numdam
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.
Motivés par les travaux de Chmutov, de Duzhin et de Lando sur les invariants de Vassiliev, nous définissons un polynôme sur les graphes avec poids qui contient, comme spécialisations, les invariants chromatiques avec poids, mais contenant également beaucoup d’autres invariants classiques dont le polynôme de Tutte et le polynôme assorti. Il donne également la généralisation de la fonction symétrique du polynôme chromatique présentée par Stanley. Nous étudions sa complexité et prouvons des résultats de dureté pour des classes très restreintes de graphes.
@article{AIF_1999__49_3_1057_0,
author = {Noble, Steven D. and Welsh, Dominic J. A.},
title = {A weighted graph polynomial from chromatic invariants of knots},
journal = {Annales de l'Institut Fourier},
pages = {1057--1087},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {49},
number = {3},
year = {1999},
doi = {10.5802/aif.1706},
mrnumber = {2000h:05066},
zbl = {0917.05025},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.5802/aif.1706/}
}
TY - JOUR AU - Noble, Steven D. AU - Welsh, Dominic J. A. TI - A weighted graph polynomial from chromatic invariants of knots JO - Annales de l'Institut Fourier PY - 1999 SP - 1057 EP - 1087 VL - 49 IS - 3 PB - Association des Annales de l’institut Fourier UR - http://geodesic.mathdoc.fr/articles/10.5802/aif.1706/ DO - 10.5802/aif.1706 LA - en ID - AIF_1999__49_3_1057_0 ER -
%0 Journal Article %A Noble, Steven D. %A Welsh, Dominic J. A. %T A weighted graph polynomial from chromatic invariants of knots %J Annales de l'Institut Fourier %D 1999 %P 1057-1087 %V 49 %N 3 %I Association des Annales de l’institut Fourier %U http://geodesic.mathdoc.fr/articles/10.5802/aif.1706/ %R 10.5802/aif.1706 %G en %F AIF_1999__49_3_1057_0
Noble, Steven D.; Welsh, Dominic J. A. A weighted graph polynomial from chromatic invariants of knots. Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1057-1087. doi: 10.5802/aif.1706
Cité par Sources :