1
$\begingroup$

Are there any internally 6-connected planar triangulations other than the icosahedron all of whose distinct 4-colorings consist of exactly 6 Kempe chains, one for each of the 6 color-pairs?

Addendum: I should have mentioned that each of the Kempe chains will be a tree because the existence of a Kempe chain that is a cycle or that has a cycle as a subgraph will necessarily break what might otherwise have been a Kempe chain of the complementary color-pair. The icosahedron has 10 distinct colorings, all of which have the stated property. The tetrahedron also has the coloring property, but it is not internally 6-connected. Both the triangle and the octahedron have the coloring property but with 4-colorings replaced by 3-colorings and 6 color-pairs replaced by 3 color-pairs. Clearly neither of those is internally 6-connected. There is a (non-regular) planar triangulation of order 5 that also has the coloring property (it has a unique 4-coloring), but it is only 3-connected.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.