Zeros of chromatic and flow polynomials of graphs (Q1402880): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
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
    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

    Identifiers