1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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:

enter image description here

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):

enter image description here

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.
$\endgroup$
6
  • $\begingroup$ Fantastic answer, thank you. Correct me if I am wrong. Basically, you can get an example of type (1) in the question and insert a vertex inside a face and get another example like yours, is that right? In which case the question begs itself, is it possible to find such examples without the vertices of degree 3? Maybe you do not know, but that is fine. One can see that in your example minus the vertex of degree 3, if you add an edge between the vertices that are odd, you get a 5-critical graph, but with the vertex of degree 3 it is no longer critical. I am running out of space, continues $\endgroup$
    – EGME
    Sep 8, 2020 at 18:07
  • $\begingroup$ You kind of see what I am after. I want to characterize the planar part of 5-critical graphs which have an edge e such that they become planar when e is removed. Now these are not necessarily maximal planar, but I am suspecting that they are “subgraphs” (kind of) of maximal planar graphs which have all vertices even except for two. In your example above, before you introduce the 3-vertex, you already have a maximal planar graph which you can understand, so in that sense, you do not need to add the 3-vertex ... but staying on topic (continues in next message) $\endgroup$
    – EGME
    Sep 8, 2020 at 18:13
  • $\begingroup$ Observe that graphs of type 2 where you have only two vertices of degree 3 colored the same, you have no “extra” vertices of degree 3. So I would like to find examples like yours without those vertices of degree 3. I am thinking they don’t exist, but of course I could very well be wrong. Perhaps I will edit the question, but perhaps it suffices to work off these comments, please suggest otherwise $\endgroup$
    – EGME
    Sep 8, 2020 at 18:18
  • $\begingroup$ Correct, I thought about that. Suppose you have a triangulation with two odd vertices and some face which is not incident with either of the two. Now take a copy of this graph with the special face being outside, and paste it inside the triangle which is not incident to the odd vertices. Would this give you a graph with two pairs of vertices which must be colored the same, the four of odd degree? And then of course, the question is whether such a graph as I describe exists? $\endgroup$
    – EGME
    Sep 8, 2020 at 18:33
  • $\begingroup$ Sorry, I deleted the comment you were replying to, because it had a flaw: it didn't increase the number of odd vertices. But then the next thing I thought of is the thing you wrote in your comment, and this does work. (To get a triangulation with two odd vertices and some face not incident to either, start with something bigger than an octahedron: for example, an octahedron where each face is subdivided into four triangles.) $\endgroup$
    – Misha Lavrov
    Sep 8, 2020 at 18:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .