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?