$\hat{I}»$-Chromatic Polynomials and Polytope Geometry

Abstract

In this paper, we investigate the notion of the \textit{$\hat{I}»$-chromatic polynomial} of a graph, which enumerates the number of distinct $L(2,1)$-colorings using colors from a prescribed finite set. We prove that the $\hat{I}»$-chromatic polynomial of a graph with $n$ vertices is a monic polynomial of degree $n$ and provide a combinatorial interpretation via lattice point enumeration within the framework of inside-out polytopes. Moreover, we compute the $\hat{I}»$-chromatic polynomial of complete graphs $K_n$ using lattice path enumeration, and we develop a block-gap technique to derive the $\hat{I}»$-chromatic polynomials for complete bipartite and multipartite graphs. Our approach unifies geometric, combinatorial, and algebraic methods to provide a systematic treatment of $\hat{I}»$-colorings across various families of graphs.