Zeros of chromatic and flow polynomials of graphs (Q1402880): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:14, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Zeros of chromatic and flow polynomials of graphs |
scientific article |
Statements
Zeros of chromatic and flow polynomials of graphs (English)
0 references
31 August 2003
0 references
The chromatic polynomial \(P(G,k)\) of a graph \(G\) is the number of colorings of \(G\) using a set of \(k\) colors, when \(k\) is a natural number. Thus the chromatic number of \(G\) is the smallest natural number which is not a root of the chromatic polynomial. The present attractive paper surveys what is known about (non-integer) roots. If \(G\) is planar, then \(P(G,k)\) counts the number of nowhere zero \(k\)-flows, and this generalizes to the flow polonomial of an arbitrary graph. Roots of flow polynomials are also surveyed in this paper. Some of these results are generalized to matroids, and a number of intriguing unsolved problems are discussed.
0 references
chromatic polynomial
0 references
colorings
0 references
chromatic number
0 references
matroids
0 references