Planar graphs with least chromatic coefficients Original Research Article

A λ-coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. The number of distinct λ-colorings of an n-point and e-edge graph G can be expressed by the chromatic polynomial P(G; λ) = ∑ni=1(−1)n−iai(G)λi, where ai(G) are non-negative integers. Let Ωp′(n,e) be the collection of all planar n-point and e-edge graphs and Ωp(n,e) be the connected graphs of Ωp′(n,e). This paper characterizes the graphs G in Ωp(n,e) and Ωp′(n,e) with the least coefficients ai(G) of P(G;λ), for all i.