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?