# How many coloring schemes are there in this map?

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.

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

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