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

Background 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 × 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. Methods We use a recursive block decomposition of F n × 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 ψ ( k ) , which governs both the recurrence relation and the closed-form expression for the chromatic polynomial. Results We establish the recurrence relation P n ( k ) = ψ ( k ) P n − 1 ( k ) and the closed-form expression P n ( k ) = ψ ( k ) n − 2 P 2 ( k ) , where ψ ( k ) = k 4 − 8 k 3 + 26 k 2 − 41 k + 26 . We prove that the chromatic number is χ ( F n × P 2 ) = 3 . The transition polynomial ψ ( k ) has exactly two real roots, both lying in the interval 2 , 3 . The asymptotic behavior is given by lim n → ∞ | P n ( k ) | 1 n = | ψ ( k ) | for fixed k with P 2 ( k ) ≠ 0 . Numerical computations for selected integer values of k confirm the recurrence and closed-form formula. Conclusions This work provides an algebraic characterization of the chromatic polynomial of F n × 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.