We focus on the faces and not the vertices.
There are lower and upper bounds
[1]
for the chromatic number
The famous 4-color theorem states that four colors are always sufficient for a planar graph. But it remains an NP - complete problem (see Chapter 19, Complexity Theory) to find out for a given graph if perhaps an even better solution smaller than the theoretically guaranteed bound exists. A greedy coloring-algorithm is not guaranteed to find optimal solutions. Actually it is known that for example the icosahedron can be appropriately colored with only 3 colors, and our straight-forward deterministic approach deliveres a suboptimal solution with 4 colors.
Therefore some probabilistic methods (see [Mol01]) are preferred. We used a quite simple 'naive probabilistic coloring procedure' algorithm to achieve the results about the chromatic numbers. Take them with a grain of salt (there are cases where a deterministic approach immediately finds the optimal result whereas our probabilistic algorithm has got problems).
Let's have a closer look at the details of our procedure. For now one probabilistic round followed by an uncoloring of faces having neighbours of the same color and then finally a greedy fillment is used. Improved methods could for example involve eagier (more than necessary) throwing away of in principle valid color values to establish a smooth, slow but perhaps more substantial construction as well as multiple iterated randomized runs instead of the greedy end.
Another possibility might be based on backtracking.
In a next step one could construct the chromatic polynomial containing the number of possible solutions for various numbers of overall colors. And there are connections (see [Ada94], Chapter 10, Knots and Links and [God00]) to the so called (Di)Chromatic, Tutte and Rank (edge deletion and contraction) polynomials of a graph. Besides spanning trees, arc-transitivity and graph parameters such as the size of the largest clique or the size of the largest independent set (that is inducing an empty subgraph) etc. could be determined.
The Pólya counting theorem and cycle index stuff establish a connection to group theory (see [Cam99] and [DesignTheory]). Let g be a permutation some label set
z(g) = x1c1(g) x2c2(g) ... xncn(g)
where x1, x2 ... are indeterminates. Let G be a permutation group, then the polyhedra cycle index is defined as follows:
We are interested in counting the orbits of G on the set of functions from
Table 8.1. Polyhedra Cycle Index
| graph | Z(G) |
|---|---|
| tetrahedron | 1/12 ( x1 4 + 8x1x3 + 3x2 2 ) |
| octahedron | 1/24 ( x1 6 + 6x1 2x4 + 3x1 2x2 2 + 6x2 3 + 8x3 2 ) |
| cube | 1/24 ( x1 8 + 8x1 2x3 2 + 9x2 4 + 6x4 2 ) |
| icosahedron | 1/60 ( x1 12 + 24x1 2x5 2 + 15x2 6 + 20x3 4 ) |
| dodecahedron | 1/60 ( x1 20 + 20x1 2x3 6 + 15x2 10 + 24x5 4 ) |
In how many different ways (up to rotations) can the vertices of an octahedron be colored with m different colors? Taking each color to be a figure of weight 0, the figure-counting series is simply m, and the number of orbits is
1/24 (m6 + 3m4 + 12m3 + 8m2).
Well, of course those aren't all proper colorings, and in general we better work on edge labels for the groups and perhaps restrict the colorings for the edges starting from the same face to have identical value (thereby specifying some face coloring).
See [Kre00] for an application of Gröbner bases and Buchberger's algorithm dealing with a 3-coloring, but beware of the theoretical computational complexity (see as well Chapter 19, Complexity Theory).