Maple's GraphTheory:-ChromaticNumber function says the chromatic number is 4. Here's one possible 4-colouring. ![alt text][1] [1]: http://www.math.ubc.ca/~israel/problems/dodeca.jpg