4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Your question is not quite clear. The requirement of 4-colorability still holds, because it is implicit in the first condition. Unique 4-colorability is dropped as a requirement, but is it forbidden? Also, if you drop that requirement it becomes important to specify if the Kempe chain condition must hold for all proper 4-colorings, or just for one. $\endgroup$
    – Leen Droogendijk
    Commented Jun 1, 2015 at 6:36
  • $\begingroup$ Finally, what about planarity? If it is not required, what does the fourth condition mean? On the other hand, if it is required the fourth condition is redundant: if there are vertices inside (and outside) a triangle, the vertices of the triangle make a cut set of size 3, contradiction the fifth condition. $\endgroup$
    – Leen Droogendijk
    Commented Jun 1, 2015 at 6:36
  • $\begingroup$ Thank you for your revisions and clarifications. I will revise the question to address your concerns. Every graph that is four-colorable is a triangulation. It has been shown that every such graph can be constructed from $K_4$ by inserting vertices inside triangles. Thus, my four condition, once stated a little more clearly, does in fact exclude uniquely colorable graphs. I will emphasize that the graphs must be planar. And I will restate the connectivity condition to indicate merely minimum-degree five. $\endgroup$
    – Jim Tilley
    Commented Jun 1, 2015 at 18:23

2 Answers 2

Reset to default
2
$\begingroup$

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. two distinct colorings of a plane triangulation of order 9

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Yes, I find it very interesting. Thank you very much. Do you have any thoughts about whether the planar graphs must be regular, because if they do, then of course there is indeed only one solution--the icosahedron. $\endgroup$
    – Jim Tilley
    Commented Jun 1, 2015 at 18:15
  • $\begingroup$ Now that I've thought about it a bit longer, it seems to me that what you have concluded is that the two conditions of only six Kempe chains in any coloring and each Kempe chain known to be a tree imply that $G$ is a plane triangulation. That is indeed a valuable observation and a conclusion that was also reached by those studying uniquely four-colorable graphs. But since EVERY plane triangulation satisfies the equation $2m=3n-6$, where $m$ and $n$ are the number of edges and vertices, respectively, in $G$, I don't think the set of possible $G$ has been narrowed by this analysis. $\endgroup$
    – Jim Tilley
    Commented Jun 1, 2015 at 21:02
  • $\begingroup$ The requirement that $G$ be a plane triangulation was not in your original question, at least not explicitly and there was some unclarity about the restrictions you wanted to impose. Indeed, in the current state of the question, this does not narrow down the solutions. I will think about this a bit more, but probably will be unable to come up with a complete solution. $\endgroup$
    – Leen Droogendijk
    Commented Jun 2, 2015 at 5:51
  • $\begingroup$ Agreed. The question should have specified that G has to be a plane triangulation. And even as stated now, it is not necessary to specify all the conditions because, as you've pointed out, some are derivable from others. However, the various conditions are mutually consistent and help fix the problem in someone's mind. I believe this is a difficult problem and that is why I have asked if anyone knows of published work that bears on it. Thank you for your thoughts. $\endgroup$
    – Jim Tilley
    Commented Jun 2, 2015 at 7:45
  • $\begingroup$ In the hope of finding mechanisms that generalize I worked on some small size examples. Apart from what I added to the partial answer I did not find a lot. The problem is interesting but I will leave it now. $\endgroup$
    – Leen Droogendijk
    Commented Jun 3, 2015 at 17:38

You must log in to answer this question.

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