Two-way bounding Problem 4

Partial Solution

To a first approximation \(\chi(M)\) is the larger of \(\chi(P)\) and \(\chi(G)\).

You might have thought that you need one more color, to deal with the possibility that the connector edge joins two nodes with the same color. If so, take a concrete example graph illustrating this situation and think about how you might modify the coloring to remove the problem. Remember that the color names are arbitrary. So if you give me a coloring with blue, red, and yellow, it's basically the same coloring if I change all the blue nodes to green.

For this problem, you should be able to get an exact answer, not just an upper or lower bound.

If you are having trouble writing "the larger of \(\chi(P)\) and \(\chi(G)\)" as a formula without breaking into cases, try using the max function. An answer with cases isn't wrong, but it's less elegant since there is a good alternative. Also, you'll end up using the max function a lot in engineering applications.

When you think you have a method that works for typical graphs, see if it needs to be modified to handle any special cases. Think about graphs that are extreme on some property, e.g. very small, many edges (e.g. complete graphs), few edges (e.g. no edges).

In your justification, did you argue both the upper and lower bounds? The upper bound can be based on your method for coloring the combinated graph. The lower bound argument will need to explain why it can't be done with fewer colors.

When you've fixed the above issues, look at the full solution.