Chromatic invariants for finite graphs: Theme and polynomial variations
type: Item
instance of: scholarly article
title: Chromatic invariants for finite graphs: Theme and polynomial variations
zbMATH Open document ID: 0831.05028
DOI: 10.1016/0024-3795(95)00248-P
author: François Jaeger
author: Pierre de la Harpe
published in: Linear Algebra and its Applications
publication date: 1995-11-09T00:00:00Z
review text: The value \(P_X (q)\) at an integer \(q \geq 1\) of the chromatic polynomial of a finite graph \(X\) is the number of morphisms from \(X\) to the \(q\)-clique \(K_q\). Generalized chromatic invariants of \(X\) are obtained by counting morphisms from \(X\) to the \(q\)-th graph of a given sequence \(Y_* = (Y_q)_{q \geq 1}\). We give criteria on \(Y_*\) for the corresponding invariant to be polynomial, to be a matroid invariant, and to give rise to recursive computations. We also investigate weighted extensions of chromatic invariants, and applications to signed graphs and links in 3-space. Most of our work is an investigation of several examples. Two open problems are formulated.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05E99
zbMATH DE Number: 803768
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: finite graph
zbMATH Keywords: morphisms
zbMATH Keywords: chromatic invariants
zbMATH Keywords: matroid invariant
zbMATH Keywords: signed graphs
zbMATH Keywords: links in 3-space
zbMATH Keywords: problems
MaRDI profile type: Publication
cites work: Q3050437
cites work: Q3241211
cites work: Q4195000
cites work: Orientability of matroids
cites work: Set colourings of graphs
cites work: A note on the star chromatic number
cites work: Generalized k-tuple colorings of cycles and other graphs
cites work: Q3992965
cites work: Q3218138
cites work: Knots
cites work: Topology of series-parallel networks
cites work: Q4040797
cites work: The chromatic number and other functions of the lexicographic product
cites work: Graph invariants related to statistical mechanical models: Examples and problems
cites work: Spin models for link polynomials, strongly regular graphs and Jaeger's Higman-Sims model
cites work: Strongly regular graphs
cites work: Q4027162
cites work: Strongly regular graphs and spin models for the Kauffman polynomial
cites work: A polynomial invariant for knots via von Neumann algebras
cites work: On knot invariants related to some statistical mechanical models
cites work: On a certain value of the Kauffman polynomial
cites work: Generalized chromatic polynomials
cites work: State models and the Jones polynomial
cites work: A Tutte polynomial for signed graphs
cites work: Polynomials for Links
cites work: Q3880849
cites work: Generosity and Characters of Multiply Transitive Permutation Groups
cites work: Q3819084
cites work: Q4873773
cites work: Being Hamiltonian is not a Tutte invariant
cites work: n-tuple colorings and associated graphs
cites work: A spanning tree expansion of the Jones polynomial
cites work: Q5788382
cites work: On dichromatic polynomials
cites work: Q4111952
cites work: Theory of Matroids
cites work: On graph invariants given by linear recurrence relations
description: scientific article; zbMATH DE number 803768