This paper proposes a new Chaotic Binary Salp Swarm Algorithm (CBSSA) to solve the graph coloring problem. First, the Binary Salp Swarm Algorithm (BSSA) is obtained from the original Salp Swarm Algorithm (SSA) using the S-Shaped transfer function (Sigmoid function) and the binarization method. Second, the most popular chaotic map, namely logistic map, is used to replace the random variables used in the mathematical model of SSA. The aim of using chaotic map is to avoid the stagnation to local optima and enhance the exploration and exploitation capabilities. We use the well-known DIMACS benchmark to evaluate the performance of our proposed algorithm. The simulation results show that our proposed algorithm outperforms other well-known algorithms in the literature.