3-coloring of specific planar graphs

Question

I've got a specific type of the planar graph and I found it interesting to search for an algorithm which will color its vertices legally. About this type of graph, it's very easy and cool:

Consider any tree $T$ with $n>2$ vertices and $k$ leaves. Let's denote $G(T)$ a graph constructed from $T$ by connecting its leaves into $k$-cycle in such way that $G(T)$ is planar.

And the problem I came up with is to color $G(T)$ with $3$ colors. Clearly, $G(T)$ as a planar graph, is $4$-colorable, but I think (don't have a proof) that it is almost always $3$-colorable due to its simplicity. Almost always means that only if $T$ is a star and only with odd number of leaves, then $G(T)$ is not $3$-colorable.

I am looking for some algorithm $3$-coloring this graph, or maybe proof of my assumptions that this class of planar graphs is $3$-colorable which could be transformed into an algorithm. I would be very very grateful for any help, hints.

In case I wasn't clear enough I'll give an example:

Let T be a tree with edges E(T) = { {1,2}, {2,3}, {2,4}, {4,5} } and then E(G(T)) = sum of the sets: E(T) and { {1,5}, {5,3}, {3,1} }, since we are connecting leaves 1,5,3 into a cycle.

Answer 1

Added 4/22/13: I've rewritten this almost entirely, to correct a serious mistake I'd made at the very outset of the original proof. I think what I've posted now is correct. (end of addition)

As nvcleemp noted, one should start with a 2-coloring (Black and White) of the tree and, if the number of leaves is even, simply change every other leaf around the cycle to a third color (Red). It's only if there is an odd number leaves that we have to do something fancier. To handle that case, it's helpful to introduce a tiny bit of terminology: Let's call the vertices that leaves are connected to "buds."

We'll start with a little lemma:

If the tree is not a star, then there are at least two buds for which the cycle traversing the leaves passes consecutively through those buds' leaves.

Proof:

It's easy to see that this is true if there are only two buds. The rest is by induction, which is easiest to picture if you imagine the graph deformed so that the cycle through the leaves is a circle. Suppose there's a bud for which the cycle does not pass consecutively through its leaves. Picture that bud as being at the center of the circle and two of its non-consecutive leaves at 12:00 and 6:00 on the circle, connected to the bud by radii. The non-consecutiveness means there are other buds connecting to other leaves on each side of the diameter just drawn. This means there is a smaller tree on each side (including the bud and two leaves of the diameter), so induction applies. One of the two consecutive-leaf buds for each side may be the bud at the center of the circle, but that still leaves at least one bud on each side for which the cycle passes through its leaves consecutively.

We're now in position to complete the proof of 3-coloring for non-stars in the case of oddly many leaves.

Pick one of the buds for which the cycle passes consecutively through its leaves. (The lemma guarantees us two, but we only need one.) Change its color to Red. Skipping its leaves for the moment, and starting with the "next" leaf (say running clockwise), turn every other leaf Red until you get back around to the Red bud's leaves, at which point you just need to alternate Black and White. (Note, this works even for the "easy" case where the number of leaves is even.)

Note: David Eppstein has given a different, inductive proof at the cross posting noted here in an answer/comment by fidbc.

Answer 2

Assuming the tree is given as well, you can start from a 2-colouring of the tree. Next you change every alternating vertex on the cycle to get a 3-colouring. This always works if $k$ is even. There might be some conflicts when $k$ is odd, but you can then change the neighbouring vertex in the tree to the third colour. This might give some other conflicts, but I think a small case study will show the cases that lead to a problem, and I would guess that the star is indeed the only one where this gives a problem.

Answer 3

a different approach would be to consider a planar embedding of the graph G into the euclidean plane and then proceed as follows:

as long as there are pairs of odd "faces" with a common edge (i.e. cycles with empty interior or the cycle with empty outside), remove their common edge and insert it into a second graph H.

If neither the original graph G (after removing the edges of H), nor H contain odd cycles, then a three-coloring exists and, one could first apply a two-coloring (say with black and white) to G without the edges of H and then apply a "skip-coloring" to the edges in H; by skip-coloring I mean a two-coloring with one opaque color (say red) and a transparent "color".

The idea of skip-coloring can also be applied to resolving conflicts in the coloring of more general graphs.

Pairing up adjacent odd cycles can be solved with matching.

Answer 4

It seems that the statement is true even without the assumption that the graph is planar. Actually, let $T$ be a tree which is not a star, and let $C$ be a cycle on all the leaves of $T$; then the graph $T\cup C$ is 3-colorable.

We will also call the vertices that leaves are connected to "buds". Let us fix the direction in $C$ and call it `clockwise' (this has no geometrical sense); all the arcs we will consider are clockwise.

As $T$ is not a star, there are at least two buds. Let $v$ be one of them, and let $a_1,\dots,a_d$ be all its leaves enumerated in the clockwise order. Since there are other buds, we may assume that $a_1$ is not the clockwise neighbor of $a_d$.

Color all the vertices of $T$ except for $v$ and $a_1,\dots,a_d$ in two colors, black and white, and paint $v$ in red. Now we will paint $a_i$'s in black and white and recolor some other vertices of $C$ in red in order to obtain a proper coloring. All we need is to check that the neighboring vertices of the cycle have different colors.

Consider the arc $(a_d,a_1)$ (it does not contain $a_d$ and $a_1$, neither other $a_i$'s). Paint its first, third, etc. vertices in red, and then paint $a_1$ in a color different from that of its counterclockwise neighbor. Repeat this procedure for the arc $(a_1,a_2)$, then for $(a_2,a_3)$, and so on. We get the desired coloring.

Answer 5

The complete graph   $K_4$   (the graph of the edges of a tetrahedron) is a counter-example, it requires exactly $4$ colors, no less.