Two-way bounding Problem 4

Hints for the construction

Notice that the picture is only one example of graphs we might pick for P and G. You might want to start by experimenting with these particular graphs, but your final solution must work for any pair of graphs.

A good way to think about this problem is as algorithm construction. I give you a pair of graphs, with some random shape and chromatic number. You need to determine the chromatic number of the joined graph.

Imagine that the input graphs have been already colored with their minimum numbers of colors. How would you create a coloring for the joined graph, by adapting the colorings of the two input graphs?

Hints for the formula

Remember that a formula can break into cases. That's not required for this problem, but you may find it helpful if you don't see how to write a single equation that covers everything.

Hints for the justification

Don't forget to explain why your answer is correct.