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.
Best Answer
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:
Proof:
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.