Maximum chromatic polynomial of 3-chromatic blocks Original Research Article

In this paper it is proved that if the chromatic polynomial P(G; λ) is maximum for λ = 3 in the class of 3-chromatic 2-connected graphs G of order n, then G is isomorphic to the graph consisting of C4 and Cn−1, having in common a path of length two for every even n ⩾ 6. This solves a conjecture raised in (Tomescu, 1994). Also, the fourth maximum chromatic polynomial P(G; λ) for λ = 3 in the class of 2-connected graphs of order n and all extremal graphs are deduced for every n ⩾ 5.