Generalized Chromatic Polynomials of Cycles and uni-cyclic Graphs

Abstract

In \cite{R81}, Read obtained an explicit formula for the generalized chromatic polynomials of cycle graphs using the classical deletion-contraction principle. In this paper, we take a linear-algebraic approach and present a new proof of Read's formula by realizing the generalized chromatic polynomials of cycle graphs as traces of certain linear operators. As an application of this approach, we also derive explicit formulas for the generalized chromatic polynomials of uni-cyclic graphs.