5
$\begingroup$

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, 

Missing["NotAvailable"]

is returned.

I have also tried, for example

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

which causes Mathematica to hang.

Is there another way?

Thanks.

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).

Improve this question
$\endgroup$
8
  • 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, 2015 at 6:45
  • 1
    $\begingroup$ @AthanasiosEvangelou You should definitely report the crash to Wolfram support. $\endgroup$
    – Szabolcs
    Sep 22, 2015 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, 2015 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, 2015 at 2:48
  • 1
    $\begingroup$ @ilian Maybe this is missing from GraphData because it took too long to compute then? $\endgroup$
    – Szabolcs
    Sep 24, 2015 at 8:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.