Many problems concerning the optimal evaluation of sparse derivative matrices can be formulated as graph coloring problems. In this talk, we focus on acyclic coloring, which is a restriction on the classic (proper) coloring problem, as well as the further restricted notion of star coloring, both of which arise in the area of sparse Hessian evaluation. In particular, we focus on classes of graphs for which different restricted coloring problems share the same set of solutions. We give characterizations for each of the following classes of graphs.
- The graphs for which every proper coloring is also an acyclic coloring.
- The graphs for which every proper coloring is also a star coloring.
- The graphs for which every acyclic coloring is a star coloring.
These characterizations are useful in that any algorithm for the less restricted coloring problem on these classes may also be used to solve the more restricted version. In some cases, these results directly imply efficient algorithms for finding optimal acyclic and star colorings, while in other cases they allow us to leverage well-established heuristic techniques designed for finding optimal proper colorings. Surprisingly, these results also reveal new connections between some very well-studied classes of graphs. If time permits, we'll also outline a linear time algorithm for finding optimal acyclic and star colorings on the class of cographs.