On the number of proper $k$-colorings in an $n$-gon

Abstract

We define an $n$-gon to be any convex polygon with $n$ vertices. Let $V$ represent the set of vertices of the polygon. A proper $k$-coloring refers to a function, $f$ : $V$ $\to$ $\{1,2,3,...k\}$, such that for any two vertices $u$ and $v$, if $f(u)=f(v)$, $u$ is not adjacent to $v$. The purpose of this paper is to develop a recursive algorithm to compute the number of proper $k$-colorings in an $n$-gon. The proposed algorithm can easily be solved to obtain the explicit expression. This matches the explicit expression obtained from the popular conventional solutions, which confirms the correctness of the proposed algorithm. Often, for huge values of $n$ and $k$, it becomes impractical to display the output numbers, which would consist of thousands of digits. We report the answer modulo a certain number. In such situations, the proposed algorithm is observed to run slightly faster than the conventional recursive algorithm.

arXiv comment8 pages, 2 tables