Chromatic polynomial of ladder graph

Abstract

The chromatic polynomial is one of the common sections in graph colourings, which is used in algebraic graph theory. The initial definition of the chromatic polynomial came from George David Birkhoff in 1912. It counts the number of graph colourings as a function of the number of k distinct colours in such a way that no two adjacent vertices are assigned the same colour. There are some general formulas for the number of chromatic polynomials PG(k) of a graph G. Most chromatic polynomials are obtained from the inspection and the Deletion-Contraction method. Our work focuses on ladder graphs (closed ladder graph) (CLₙ) and an open ladder graph (OLn ) obtained by eliminating the side edges of the ladder graph. In this study, the general formula of the chromatic polynomial for open ladder graph (OLn) for n ≥ 3 and closed ladder graph (CLn) for n > 1 is obtained by dividing the ladder graph into two graphs G₁ and G₂ by the common edge. We can identify a pattern of chromatic polynomials for both types of ladder graphs. The general formula of CLn for n > 1 can be recognized as, PCLn (k) = k(k − 1)(k2 − 3k + 3) n−1 . Also, the general formula of OLn for n ≥ 3 can be recognized as, POLn = k(k − 1) 5 (k 2 − 3k + 3) n−3 . The mathematical induction method can prove the correctness of the obtained general formulas.