The star-chromatic number of snarks and its variants

Abstract

The star coloring problem is a specialized form of vertex coloring that arises in certain computational contexts, such as when computing Hessians using automatic differentiation or finite differencing. This problem is particularly relevant when exploiting both sparsity and symmetry in the computation. Automatic differentiation is a technique used to compute derivatives numerically, and finite differencing is another approach for approximating derivatives. In these computations, sparsity (a small number of non-zero elements in a matrix) and symmetry (certain patterns in the structure of the matrix) are often exploited to optimize efficiency. A proper vertex coloring of the graph G is considered as star coloring if it uses at least three different colors for every path of length three. The star chromatic number of a graph G, denoted as χ _s  (G), is the minimum number of colors needed to accomplish the star coloring of the given graph G. This paper focuses on determining χ _s  (G) for graphs belonging to the family of snarks and their variants.