The function IGChromaticNumber in IGraph works great, so well, that I have been able to check the chromatic number of graphs with max degree 12 with over a thousand vertices in a relatively short amount of time. More specifically, I am able to use the function IGKVertexColoring to determine whether graphs are colorable with a given number of colors or not. However, sometimes, there is a not so large graph where these two functions get stuck. I am wondering if there is anything one can do to get these functions “unstuck”. I tried for example, renumbering the vertices of the graph, without luck. Are there any alternatives to try computing the chromatic number of a graph with 105 vertices, of max degree 12, or more specifically, to try to determine whether the graph(s) are 6-colorable? The ResourceFunction[“ChromaticNumber”] did not work (it forced-quit the kernel). And the graph is too large to try the chromatic polynomial approach. I thank you in advance for your help.
EDIT I copy and paste the example for which I want the chromatic number, which I suspect is 6. I have tried without success using IGKVertexColoring, although I don't know how long I should wait. This function tells me immediately that it is 7-colorable, and that it is NOT 5-colorable. I would like to know if it is 6-colorable, but it hangs when you try to find that out. The example is in Sparse6 format. I had to paste an image of it, otherwise the MathJax tries to interpret the string ... this string can be read with ImportString using the "Sparse6" format specification. Please suggest a better way to provide the example if you think of one.
EDIT 2 Alternatively, the graph can be obtained as follows. From GraphData, look for the “HarriesGraph”. Then take the line graph of that graph, and then take the square graph of the line graph. That is the graph in question.