On the locating chromatic number of infinite trees

Abstract

The locating chromatic number of a graph is the smallest integer n such that there exists a proper n-coloring c for which every vertex has a unique vector of distances to the color classes defined by c. If no such integer n exists, the locating chromatic number is infinite. We explore properties of the locating chromatic number of infinite graphs, focusing on sufficient and necessary conditions for an infinite tree to have a finite locating chromatic number. We conjectured that an infinite tree has a finite locating chromatic number if and only if the tree has bounded degree and is prunable. We prove that the conditions in the conjecture are sufficient and provide evidence as to why they might be necessary. Lastly, we compare the performance of our locating coloring algorithm with that of known locating coloring algorithms. Our algorithm outperforms previously known algorithms for trees with many branches.