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

BACKGROUND: 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 × P 2 remains largely unexplored despite its layered constraint structure, presenting a clear gap in the literature. METHODS: 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 ψ ( k ) , which governs the recurrence relations and closed-form expressions. 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 . The chromatic number is proven to be χ = 3 , with real roots of ψ ( k ) located within [2,3]. Numerical validation confirms both recurrence and closed-form formulas, while asymptotic analysis shows the exponential growth of P n ( k ) is governed by ψ ( k ) , as lim n → ∞ [ P n ( k ) ] 1 n = | ψ ( k ) | . CONCLUSIONS: This research provides a comprehensive algebraic characterization of the chromatic polynomial for F n × 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.