The Chromatic Polynomial of the Scorpion Graph

Abstract

In 1912, Geory Birkhoff introduced the chromatic polynomials for planar graphs as a result of solving the four-color problem and Hassler Whitney generalized Birkhoff`s idea for any kind of graphs in 1932. It became one of the central objects in Algebraic graph theory. Let G be an undirected simple graph of order n. One can color vertices of graph G with k number of colors so that any adjacent vertices are colored differently. The chromatic polynomial P(G,k) gives the number of ways of coloring vertices of a graph using k number of colors. The chromatic polynomials have been derived for several types of graphs such as cycle, complete, ladder, null and star graphs. In our work, we present the chromatic polynomial for the Scorpion graph 〖 S〗_((n,m,l)) where n,m,l ∈Z^+. The Scorpion graph is defined by introducing tree graphs, path graphs to few levels of the ladder graph. A graph obtained from the ladder graph, L_n, with n levels for n>5 by adjoining the star graphs, K_(1,m), for each vertex on the 1st level and the nth level, and path graphs, P_(l+1), for each vertex on 2nd level to 5th level to represent the legs of the Scorpion. Then the number of vertices of the Scorpion graph is 2(n+2m+4l). In this work, we give an overview of the construction of the chromatic polynomial of ladder graph and finally chromatic polynomial of the Scorpion graph. The chromatic polynomial of the Scorpion graph 〖 S〗_((n,m,l)) is P(S_((n,m,l) ),k)=k〖(k-1)(k^2-3k+3)〗^(n-1) 〖(k-1)〗^(4m+8l) for k∈N. The Deletion – Contraction method has been used to give the combinatorial proof to the above result. As a future work, we are planning to generalized this work for different body shapes.