Chromatic invariants for finite graphs: Theme and polynomial variations (Q1899442): Difference between revisions
From MaRDI portal
Latest revision as of 17:37, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic invariants for finite graphs: Theme and polynomial variations |
scientific article |
Statements
Chromatic invariants for finite graphs: Theme and polynomial variations (English)
0 references
9 November 1995
0 references
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.
0 references
chromatic polynomial
0 references
finite graph
0 references
morphisms
0 references
chromatic invariants
0 references
matroid invariant
0 references
signed graphs
0 references
links in 3-space
0 references
problems
0 references
0 references