1
$\begingroup$

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.

a possibly 6 colorable graph

$\endgroup$
  • $\begingroup$ Is it possible to provide an example of a graph where the computation hangs? $\endgroup$ – MassDefect Jun 23 at 18:44
  • $\begingroup$ @MassDefect I can supply a Graph6 formatted example ... I will edut the question to include the example, unless you suggest a better alternative. Let me know what is best, I will wait for your answer ... or I could paste the edge list as well ... $\endgroup$ – EGME Jun 23 at 18:49
  • $\begingroup$ I thought perhaps you had created the graph programatically in Mathematica and would be able to provide a short code that generates the graph, but it sounds like that's not the case. If there's a relatively concise version of your graph that you can post, it would probably be worthwhile. Between the Graph6 version or list of edges, probably whichever one is shorter is best. $\endgroup$ – MassDefect Jun 23 at 18:58
  • $\begingroup$ @MassDefect How do you paste a string which has special characters, so that MathJax won’t try to interpret them??? $\endgroup$ – EGME Jun 23 at 19:05
  • $\begingroup$ I have limited internet access these days and won't check the site often (nor will I be able to respond). But maybe it's useful to note that IGraph/M currently uses a SAT formulation of graph coloring, along with forcing colours on a clique to break the symmetry of the problem and speed up the computation (see ForcedColoring option). $\endgroup$ – Szabolcs Jun 23 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.