Maximum chromatic polynomials of 2‐connected graphs
Ioan Tomescu · Journal of Graph Theory · 1994
Abstract In this paper we obtain chromatic polynomials P(G ; λ) of 2‐connected graphs of order n that are maximum for positive integer‐valued arguments λ ≧ 3. The extremal graphs are cycles C n and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{ P(G ; λ): G is 2‐connected of order n and G ≠ C n } and all extremal graphs relative to this property, with some consequences on the maximum number of 3‐colorings in the class of 2‐connected graphs of order n having X (G) = 2 and X (G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2‐connected graphs are determined.