# Interesting planar graph coloring task - estimate colours for double planar graph

I got an interesting exercise on my course at University.

I am wondering about an answer and I would like that some people would wonder with me. Because there may be not clear answer even.

So.. as you know from four color theorem, if the graph is planar, then it is possible to color all vertices within such a graph in 4 different colors or less.

Now.. imagine graph G=(V,E), which is "double planar". That means that E = E1 u E2 in such a way that if you consider G1=(V,E1) is planar and G2=(V,E2) is planar as well. However G=(V,E) doesn't have to be planar.

And the question is.. to estimate from bottom and above the maximum number of colors which is required for such a graph to color it (with the logic as in four colors theorem = cannot exists edge with the same colors on the both ends). So imagine the worst case graph as I described and estimate it color numbers (we call it chroma number).

I hope I have described the problem clearly enough.

If anyone have some question to specify problem better feel free to ask.

If anyone would be interested in wonders please share your ideas with me. I am going to think over night and write here something tomorrow, because Professor is going to take our ideas at Thursday mid-day.

Have a nice day, and really welcome to overthink this task together :)

It is also easy to show that the complete join of $K_6$ and $C_5$ requires 9 colors.