I want to know the number of 4-colorings for all Johnson solids. This is equivalent to evaluating the flow polynomial for the corresponding polyhedral graphs at $k=4$.

I tried the following to get the data:

Table[{i, 4 GraphData[{"JohnsonSkeleton", i}, "FlowPolynomial"][4]}, {i, 92}]

But for nos. 38-43, 47, 48, 68-82,


is returned.

I have also tried, for example

FlowPolynomial[GraphData[{"JohnsonSkeleton", 38}], 4]

which causes Mathematica to hang.

Is there another way?


UPDATE As ilian pointed out in the comments, the command FlowPolynomial does in fact seem to work-the missing graph numbers just need a lot of memory and time to compute.

I tested the command on a machine with 32GB RAM to confirm ilian's value for $n=38$ (500792391843)and also got the value for $n=39$ (500453836143). But $n=40$ exhausted all the RAM and crashed the machine.

So maybe it's unrealistic to ask for the 4-colour numbers for all the Johnson graphs after all. In that case I'd be very happy to settle for approximations of the missing numbers.

EDIT I'm also interested in the same question for the Archimedean solids and their duals (Mathematica is also missing some data for these).

  • 1
    $\begingroup$ Have you tried asking Wolfram support? Is there any fundamental reason why there shouldn't be a value associated with those solids? $\endgroup$ – MarcoB Sep 21 '15 at 6:45
  • 1
    $\begingroup$ @AthanasiosEvangelou You should definitely report the crash to Wolfram support. $\endgroup$ – Szabolcs Sep 22 '15 at 10:30
  • 1
    $\begingroup$ Yes, it hangs. After 10 minutes I shut it down. But I don't know what is a reasonable computation time for a graph like this ... $\endgroup$ – Szabolcs Sep 22 '15 at 10:51
  • 2
    $\begingroup$ Might just be a long computation -- I got 500792391843 after 43 minutes and needed around 21 GB of memory. $\endgroup$ – ilian Sep 23 '15 at 2:48
  • 1
    $\begingroup$ @ilian Maybe this is missing from GraphData because it took too long to compute then? $\endgroup$ – Szabolcs Sep 24 '15 at 8:23

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.