Unique four-colorings of planar graphs and the like… I am doing research into a particular graph coloring problem and wonder if someone can direct me to published work that bears on what I’m studying.
It is known that planar graphs that are uniquely four-colorable belong to a class populated by $K_4$ (the complete graph of order $4$, a.k.a, the "tetrahedron") and any graph derived from $K_4$ by inserting vertices into triangles. There are several interesting properties of such graphs, not the least of which that they have following properties:


*

*They are plane triangulations.

*Every vertex is adjacent to vertices of the other three colors. 

*In every coloring, every Kempe chain is a tree.  

*In every coloring, there is one and only one Kempe chain for each color-pair.


I am not interested in uniquely four-colorable planar graphs per se, but in the class of planar graphs that are NOT uniquely four-colorable but which satisfy the properties above and also  


*

*In any drawing in the plane in which the graph is represented as a set of vertices and edges within an "outermost" triangle T, there are no vertices inside any triangle other than T (that is, no "separating triangles").

*They are minimum-degree $5$.


The "icosahedron" is the only member of this class that I’ve been able to construct/locate.  Does anyone know of work that has been done on this problem?  Does anyone care to speculate about whether there are any others? 
 A: This continues to be part of the research I'm doing on graph coloring.  If one relaxes the condition of "minimum degree $5$" to "$4$-connected" (that is, the triangulation $T$ must be $4$-connected rather than minimum degree $5$) but insists that the graph still be $4$-connected after an edge joining vertices of at least degree 5 is deleted to form a near-triangulation $G$, then, apart from the icosahedron, which we've previously identified as satisfying all of the conditions, there is a $T$ of order $9$ for which there are two distinct colorings, each of which is comprised of six Kempe chains, one for each of the six possible color-pairs.  Of course, all the Kempe chains are trees or there wouldn't be only six.  The following graph illustrates the two distinct colorings from which the Kempe chain claim can be verified easily. 
A: THIS IS NOT A COMPLETE SOLUTION!
Just some preliminary information you may find interesting.
Let $G$ be our graph and $n$ be its number of vertices.
The six Kempe chains come in three complementary pairs. The two chains from one pair are disjoint and cover all vertices,
so if they are trees, they have $n-2$ edges together.
Since the six Kempe chains partition the edges of $G$, the number of edges of $G$ must be $3n-6$.
Note that this result is a consequence of the second condition only. It also does not require planarity.
Let $a$ be the average degree of $G$. We get $na=2(3n-6)$ or $n=\frac{12}{6-a}$.
If we just add the condition that the minimum degree of $G$ is at least 5 (which is weaker than 5-connectivity),
we get $n\geq12$, so you certainly need not look for graphs that are smaller than the icosahedron you already found.
If we add the requirement that $G$ must be planar, the remarkable(?) occurrence of $3n-6$ immediately shows that $G$ must be a triangulation.
Let $n_1\leq n_2\leq n_3\leq n_4$ be the sizes of the color classes.
Then following inequalities hold:
$n_1\geq 3$
$n_3\leq n_1+n_2-2$
$2n_4\leq n_1+n_2+n_3-3$
This is probably not very relevant but it provides an easy proof that no examples with 13 or 14 or 17 vertices are possible.
