Four colored triangulations with two distant vertices which must be colored the same

Question

This is a follow up on a related question about planar graphs in general. In this question we wish to consider only maximal planar graphs (triangulations). It is known that

1. In any four coloring of a triangulation with exactly two odd vertices the odd vertices must be colored the same.

2. In uniquely colored triangulations some non adjacent vertices must be colored the same.

The question is whether there are other kinds of triangulations in which the coloring of two non adjacent vertices is forced to be the same, as in the above two examples. Is this known or not?

Thank you.

Answer 1

This was essentially answered in your first question, it was only obscured because the example I gave happened to be uniquely colorable. But here's a way to construct lots of other examples.

Start with a triangulation in which all degrees are even. (For example, let's start with the octahedral graph.)

Draw a line between two non-adjacent vertices and add a vertex wherever this line crosses an existing edge. This (always!) gives us a triangulation in which exactly two vertices are odd:

Those vertices, as we know, must have the same color in any $4$-coloring. However, usually such a triangulation will not be uniquely $4$-colorable, and in fact that's not true here.

Finally, just add a new vertex adjacent to the three corners of some face (any face):

There are now more than two odd vertices (no matter which face we picked). However, any $4$-coloring of this graph induces a $4$-coloring of the graph at the previous step, and vice versa (the color of the new vertex is uniquely determined). Therefore:

• The graph we get isn't uniquely $4$-colorable, because we didn't have a uniquely $4$-colorable graph before.
• The two vertices that used to be the only two odd vertices before must still have the same color in any coloring.