1
$\begingroup$

enter image description here

This map is painted in four colors. The colors of two adjacent areas cannot be the same. How many color schemes are there?

g = Graph[(Sort /@ 
     Flatten[Map[
       Thread[#[[1]] \[UndirectedEdge] #[[2]]] &, {{1, {2, 3}},
        {2, {1, 3, 4, 5}},
        {3, {1, 2, 5, 6}},
        {4, {2, 5, 7, 8}},
        {5, {2, 3, 4, 6, 7}},
        {6, {3, 5, 7}},
        {7, {4, 5, 6, 8}},
        {8, {4, 7}}}]]) // DeleteDuplicates, VertexLabels -> "Name"]

In addition, I am looking for a brute force enumeration algorithm.

$\endgroup$
4
  • 4
    $\begingroup$ Maybe you are looking for the chromatic polynomial. $\endgroup$
    – Szabolcs
    Commented Jan 18, 2020 at 10:49
  • $\begingroup$ Thank you very much for your prompt. $\endgroup$ Commented Jan 18, 2020 at 11:14
  • 3
    $\begingroup$ @Ordinaryusers68 ChromaticPolynomial[g, 4] gives 480 four-colourings $\endgroup$
    – flinty
    Commented Jul 11, 2020 at 13:24
  • $\begingroup$ In[1329]:= ResourceFunction["FindProperColorings"][g, 4] // Length Out[1329]= 480 $\endgroup$ Commented Dec 3, 2021 at 16:30

1 Answer 1

1
$\begingroup$
data = Tuples[{1, 2, 3, 4}, 8];
samedata = (Sort /@ (Flatten[
       Outer[List, {#[[1]]}, #[[2]]] & /@ {{1, {2, 3}},
         {2, {1, 3, 4, 5}},
         {3, {1, 2, 5, 6}},
         {4, {2, 5, 7, 8}},
         {5, {2, 3, 4, 6, 7}},
         {6, {3, 5, 7}},
         {7, {4, 5, 6, 8}},
         {8, {4, 7}}}, 2])) // DeleteDuplicates;
sameQ[list_] := 
 If[AnyTrue[
   Table[SameQ @@ (list[[samedata[[i]]]]), {i, 1, Length[samedata]}], 
   TrueQ], False, True]
Select[data, sameQ[#] &] // Length
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.