Chromatic Polynomials of \(C^{(3)}_n\) Graphs: Lucas Sequences, ϕ\(^n\) Asymptotics and Linear Recurrence Existence
Rogelio Lopez-Bonilla *
Department of Mathematics, Computer Science and Engineering Technology, Elizabeth City State University, Elizabeth City, NC 27909, USA.
Julian Allagan
Department of Mathematics, Computer Science and Engineering Technology, Elizabeth City State University, Elizabeth City, NC 27909, USA.
Shawn M. Langley
Department of Mathematics, Computer Science and Engineering Technology, Elizabeth City State University, Elizabeth City, NC 27909, USA.
Angel J. Clinton
Department of Mathematics, Computer Science and Engineering Technology, Elizabeth City State University, Elizabeth City, NC 27909, USA.
*Author to whom correspondence should be addressed.
Abstract
This paper investigates the chromatic structure of generalized circular chord graphs \(C^{(3)}_n\), constructed by augmenting
an n-cycle with chords at fixed offset k = 3 and diameter edges for even n. We establish a fundamental dichotomy between odd and even values of n in their 3-coloring enumeration. For odd n, we derive an explicit closed form P(\(C^{(3)}_n\), 3) = Ln +2cos(2πn/3)+2sn +2, where Ln denotes the Lucas sequence and sn satisfies a cubic recurrence. This formulation reveals golden-ratio asymptotic behavior ϕn +O(ρn), with ϕ = (1+√5)/2 and ρ ≈ 1.466 determined by the real root of λ3 +λ2 +1 = 0, positioning these graphs among rare families exhibiting algebraic growth constants. For even n, we prove via transfer matrix theory that a linear recurrence with rational coefficients must exist, though its explicit
Keywords: Chromatic polynomials, graphs, Lucas Sequences, Linear Recurrence