Chromatic Polynomials of F n× P2  Graphs: Algebraic Analysis and Scheduling Applications

Chromatic polynomials are fundamental algebraic invariants in graph theory, bridging pure mathematics and practical applications. While extensive results exist for paths and cycles, the Cartesian product $F_n\times P_2$ remains largely unexplored despite its layered constraint structure, presenting a clear gap in the literature.

We employ combinatorial decomposition and recursive block construction, applying the inclusion-exclusion principle to the eight edge constraints within each recursive unit. This analytical approach enables the derivation of the chromatic transition polynomial $\psi \left(k\right)$ , which governs the recurrence relations and closed-form expressions.

We establish the recurrence relation $P_n\left(k\right)=\psi \left(k\right)P_{n-1}\left(k\right)$ and the closed-form expression $P_n\left(k\right)={\left[\psi \left(k\right)\right]}^{n-2}{P}_2\left(k\right)$ where $\psi \left(k\right)=k^4-8k^3+26k^2-41k+26.$ The chromatic number is proven to be $\chi =3$ , with real roots of $\psi \left(k\right)$ located within [2,3]. Numerical validation confirms both recurrence and closed-form formulas, while asymptotic analysis shows the exponential growth of $P_n\left(k\right)$ is governed by $\psi \left(k\right)$ , as $\underset{n\to \infty }{lim}{\left[P_n\left(k\right)\right]}^{\frac{1}{n}}=\left|\psi \left(k\right)\right|$ .

This research provides a comprehensive algebraic characterization of the chromatic polynomial for $F_n\times P_2$ , deriving its recurrence relation and closed-form expression. Building on this foundation, we develop a novel two-period conference scheduling model where the chromatic polynomial serves as a quantitative tool to compute all conflict-free room allocations. This work demonstrates directly how structural graph theory can inform practical resource allocation systems, transforming an abstract invariant into a concrete decision-support tool.