A 2-coloring of a graph G is an assignment of 2 or fewer colors to the points of G so that no two adjacent points have the same color. The number of distinct 2-colorings of an n-point and e-edge graph G can be expressed by the chromatic polynomial P(G; 2) = ~7=1(-1 )"-iai(G)2i, where ai(G) are non-negative integers. Let 12~(n,e) be the collection of all planar n-point and e-edge graphs and I2p(n,e) be the connected graphs of I2'p(n,e). This paper characterizes the graphs G in f2p(n,e) and f2'p(n,e) with the least coefficients ai(G) of P(G;2), for all i.
1. In~oduefion
A 2-coloring is a proper coloring of the points of a graph using 2 or fewer colors. It is well known that the number of 2-colorings of G on n points and e edges is given by the chromatic polynomial P(G; 2)= ~7= 1(-1)n-iai(G)~.i, where ai(G) are non-negative integers with an(G)= 1 and an-l(G)= e. Among a given class of n-point and e-edge graphs fΒ’, we say that a graph GC~ is ai-minimum if ai(G)<.ai(G I) for all G'Ef#. Let t-2(n,e) be the collection of all connected n-point and e-edge graphs and t2p(n,e) be the set of planar graphs in f2(n,e). An important question that arises in this context is the following: Which graphs in t2(n,e) are ai-minimum for all 1 <~i<~n-2? Likewise, which graphs in t2p(n,e) are ai-minimum for all 1 <~i<~n-2? Recently, ai-minimum graphs in f2(n,e), l<~i<~n-2, have been characterized in [4].
In this paper we first consider the class f2p(n, e), the collection of all connected planar graphs. Let b(G) be the number of blocks (i.e., nonseparable components) of graph G. Define b(n, e) = max{b(H) I H E Qp(n, e)}. We prove that a graph G C f2p(n, e) is aiminimum for all 1 <<.i<~n -2 iff G is a chordal graph and b(G)=b(n,e). Next, we consider the class O~(n, e), the collection of all planar graphs. Let c(G) be the number of connected components of graph G. Since ai(G)= 0 for all i < c(G), ai-minimum