  Coloring the faces of 2-dimensional square lattice with $k$ distinct colors
such that no two adjacent faces have the same color is considered by
establishing connection between the $k$ coloring problem and a generalized
vertex model. Associating the colors with $k$ distinct species of particles
with infinite repulsive force between nearest neighbors of the same type and
zero chemical potential $\mu$ associated with each species, the number of ways
$[W(k)]^N$ for large $N$ is related to the entropy of the {\it{hard square
lattice gas}} at close packing of the lattice, where $N$ is the number of
lattice sites. We discuss the evaluation of $W(k)$ using transfer matrix method
with non-periodic boundary conditions imposed on at least one dimension and
show the characteristic Toeplitz block structure of the transfer matrix. Using
this result, we present some analytical calculations for non-periodic models
that remain finite in one dimension. The case $k=3$ is found to approach the
exact result obtained by Lieb for the residual entropy of ice with periodic
boundary conditions. Finally, we show, by explicit calculation of the
contribution of subgraphs and the series expansion of $W(k)$, that the
genenralized Pauling type estimate(which is based on mean field approximation)
dominates at large values of $k$. We thus also provide an alternative series
expansion for the chromatic polynomial of a regular square graph.
