Abstract
The implementation of a graph generator associated with the estimation of mathematical derivatives is described. The graph colouring instances are obtained as intersection graphs G Π(A) of the sparsity pattern of A∈ℜ m×n with row partition Π. The size of the graph is dependent on the row partition; the number of vertices can be varied between the number of columns (using single block row partition Π=Π1) and the number of nonzero entries of A (using m-block row partition Π=Π m ). The chromatic number of the generated graph instances satisfy . A summary of colouring results on the ColSegSet problems is presented. We also show that the main idea of the graph instance generator can be extended to general undirected graphs.
Acknowledgements
The author is indebted to Trond Steihaug who read an early draft of the manuscript and provided valuable suggestions for improvement. The author would like to thank the anonymous referees for helpful comments and criticism on the manuscript. This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) under a Discovery Grant.