# 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?

• I thought (while 4-colourings are possibly hard to find) 5-colourings are not that difficult (by us following Kempe's failed 4-colour proof)? – Hagen von Eitzen Jul 28 '16 at 19:16
• @HagenvonEitzen I need to find not coloring but graph, for which greedy algorithm gives 7-coloring. Of course that graph will be colorable with 4 or less colors. – Somnium Jul 28 '16 at 19:18
• I just wondered what th especific utility of your 6-colouring algorithm is. Is it especially efficient, compared to the backtracking needed in 5-colouring? Never mind, what I aske here that is not the question you need answered – Hagen von Eitzen Jul 28 '16 at 19:20
• How about a suitable crown graph? – Joffan Jul 28 '16 at 19:28
• @Joffan usually won't be planar – Hagen von Eitzen Jul 28 '16 at 19:31

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.
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.