Generalized Chromatic Polynomials of Cycles and uni-cyclic Graphs
math.CO
Submitted: 2026-11-05
Updated: 2026-11-05
License: http://creativecommons.org/licenses/by/4.0/
The gist: In, Read obtained an explicit formula for the generalized chromatic polynomials of cycle graphs using the classical deletion-contraction principle.
Terminology
Abstract
In, 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.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality