Is there a statement for polyhedra similar to four-color theorem?
I could only google a book called "Map Coloring Polyhedra and the Four Color Problem". Unfortunately, it's not available to read online. From what I've found, it seems to me that there is only a handful of proven facts about colorings of some polyhedra.
[ADD]: four color theorem works for every planar graph and it looks like one can make such graph corresponding to any convex polyhedron, so it seems that original OP statement holds.