Coloring puzzles


Problem:

Each face of a cube is divided into four squares. Each of the 24 squares is to be painted with one of three colors, in such a way that any two squares sharing an edge have different colors. Can this be done, and if so, can nine of the 24 squares have the same color?


Solution:

Each corner of the cube is bordered by three squares, and each square has one vertex that is also a corner of the cube. Consequently, we can partition the squares into eight groups, one per corner of the cube, where each group is comprised of the three squares attached to that corner. If three squares belong to the same group, then they must use three colors, which means that given three colors, the number of squares with the same color cannot be more than eight. However, a three coloring is possible, coloring eight squares the same color. Here's one way of doing it:


Going further:

Given some graph, where each vertex represents a face, and each edge of the graph represents a shared edge in the polyhedron, what is the minimum number of colors required, and using the minimum number of colors, what is the maximum number of faces that can have the same color?


Source:

This puzzle comes from "The Inquisitive Problem Solver." I rewrote it, as the way it was phrased originally was more confusing than necessary. I also added some additional questions.