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 :)


You are asking for bounds on the chromatic number of a graph of thickness 2. This is a rather well-studied, but as far as I know not completely solved problem.

It is rather easy to show that 12 colors are always sufficient.

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


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.