The Cat Swarm Optimization (CSO) algorithm is a relatively recent addition to the family of algorithms known as Swarm Intelligence and is based on the common behavior of cats. With the claim of improved performance in finding the global best solutions, it is tested in solving the well-studied Graph Coloring Problem (GCP). The goal in GCP is to color a graph using the least number of colors possible such that no connected vertices share the same color. Aside from solving GCP, the effect of a fitness function in the efficiency of CSO is also assessed. Experiment results showed that CSO was able to solve all GCP instances. Furthermore, CSO was able to find the optimal solution for some graph types. Also it is shown that the nature of the solution found is affected by the fitness function used. These results indicate that CSO is a feasible algorithm in solving GCP.