Finding The Chromatic Polynomial Of Cayley Graphs Using The Tutte Polynomial

Abstract

In Algebraic Graph Theory, Biggs \([2]\) gives a method for finding the chromatic polynomial of any connected graph by computing the Tutte polynomial. It is used by Biggs \([2]\) to compute the chromatic polynomial of Peterson’s graph. In \(1972\) Sands \([4]\) developed a computer algorithm using matrix operations on the incidence matrix to compute the Tutte Polynomial. In \([1]\), Anthony finds the worst-case time-complexity of computing the Tutte Polynomial. This paper shows a method using group-theoretical properties to compute the Tutte polynomial for Cayley graphs which improves the time-complexity.