How I can find planar graph for which greedy vertex coloring find coloring with 7 colors? I have wrote an algorithm for planar graph coloring with at most 6 colors in linear time. Now I want to test it. I thought that it will be good to test on graph which standart greedy coloring fail to color with 6 colors.
I have tough time even with finding graph for which greedy vertex coloring find coloring with 5 colors. All graphs I can construct, greedy algorithm colors with 4 colors no matter of vertex order.
How I can find planar graph for which greedy vertex coloring find coloring with 7 colors?
 A: We can construct a connected plane graph $G_n$ such that the greedy algorithm (with a suitable vertex order produces a colouring using $n$ colours, and such that tall vertices are adjacent to the unbounded face.
This is clear for $n=1$.
Assume $n>1$ and we already have $G_{n-1}$. Let $G_n$ consist of $n-1$ separate copies of $G_{n-1}$ and an additional vertex $v$.
For $1\le i\le n-1$, add an edge from $v$ to a vertex of the $i$th copy of $G_{n-1}$ that is assigned colour $i$ by greedy colouring.
On this $G_n$, perform the greedy algorithm by first running over the copies of $G_{n-1}$ in the order defined for them, and finally visit $v$. This will lead to an $n$-colouring of $G_n$. Also, all vertices of $G_n$ are adjacent to the unbounded face.
A: Just to illustrate @Hagen von Eitzen genius answer, here image with graph, for which greedy algorithm gives 5-coloring. I used as base case complete graph $K_4$ so result graph is not so large.
Here image:

And after squeezing it I got this 5-colored graph with only 6 vertices:

