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?

  • $\begingroup$ 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)? $\endgroup$ – Hagen von Eitzen Jul 28 '16 at 19:16
  • $\begingroup$ @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. $\endgroup$ – Somnium Jul 28 '16 at 19:18
  • $\begingroup$ 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 $\endgroup$ – Hagen von Eitzen Jul 28 '16 at 19:20
  • $\begingroup$ How about a suitable crown graph? $\endgroup$ – Joffan Jul 28 '16 at 19:28
  • 1
    $\begingroup$ @Joffan usually won't be planar $\endgroup$ – 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.

  • $\begingroup$ Thank you! It's genius. I have made a picture which illustrates your principle. $\endgroup$ – Somnium Jul 28 '16 at 19:55

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:

5-colored graph

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

5-colored graph 2


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.