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

Chromatic polynomials are fundamental algebraic invariants in graph theory, linking structural properties of graphs with algebraic and enumerative information. While extensive results exist for paths, cycles, and several classical graph products, the Cartesian product $F_n\times P_2$ , where $F_n$ is the friendship graph, and $P_2$ is the path on two vertices, has received limited direct attention despite its layered triangular structure.

We use a recursive block decomposition of $F_n\times P_2$ . After fixing the colors of the two central vertices, we derive the local extension count for the newly attached block through a structured combinatorial case analysis. This yields the transition polynomial $\psi \left(k\right)$ , which governs both the recurrence relation and the closed-form expression for the chromatic polynomial.

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.$ We prove that the chromatic number is $\chi (F_n\times P_2)=3.$ The transition polynomial $\psi \left(k\right)$ has exactly two real roots, both lying in the interval $[2,3]$ . The asymptotic behavior is given by $\underset{n\to \infty }{lim}|P_n\left(k\right){|}^{\frac{1}{n}}=|\psi \left(k\right)|$ for fixed $k$ with $P_2\left(k\right)\ne 0$ . Numerical computations for selected integer values of $k$ confirm the recurrence and closed-form formula.

This work provides an algebraic characterization of the chromatic polynomial of $F_n\times P_2$ through a recursive block structure and a single transition polynomial. The results also support an illustrative two-period scheduling interpretation, where the chromatic polynomial counts feasible room assignments under explicitly stated conflict constraints.