Counting Selective Colorings on an n-Cycle

A coloring on a graph is an assignment of some label to each vertex of the graph. A proper coloring is a coloring in which any two connected vertices are not given the same label. It is sometimes relevant in graph theory to attempt to count the number of proper colorings that can be done on a graph given some number of colors. In this paper, we extend the idea of a proper coloring and give it a generalization. We call the resulting type of coloring a ``selective coloring." The selective coloring is defined by a selective function, φ, which maps available colors onto other available colors such that no color and its image under φ may be adjacent under the selective coloring. The number of selective colorings are found for a cycle of 10 vertices under a particular selective function. This number is generalized to any n vertices. A pattern among these numbers is conjectured and then proved. Finally, a method of generalizing the number of selective colorings on n-cycles is theorized for arbitrary selective functions.