Two-way bounding Problem 4



Note: most of the time, the chromatic number will be equal to \(\max(\chi(P),\chi(G))\). Forcing \(\chi(M)\) is only important when P and G both have chromatic number 1. That is, when neither P nor G contains any edges.


Lower bound: P is a subgraph of M, so \(\chi(M) \ge \chi(P)\). Similarly, \(\chi(M) \ge \chi(G)\). We also know that \(\chi(M) \ge 2\), because M contains at least one edge: the one connecting P to G. So \(\chi(M)\ge \max(\chi(P),\chi(G),2)\).

Upper bound: Suppose that \(k = \max(\chi(P),\chi(G),2)\). We can color P with k colors, because \(k \ge \chi(P)\). Similarly, we can color G with the same k colors.

Now, suppose that x and y are the nodes connected by the new edge. If we have already assigned them different colors, then we are done.

If x and y have the same color, we must swap two of the color labels in G's coloring. That is, if x and y have color C, we find some other color D in our set. This second color D always exists because we've forced k to be at least 2. In the graph G, we then relabel each C node with D and each D node with C. Now x and y have different colors.

Now we have a coloring of M with k colors. So So \(\chi(M)\le k = \max(\chi(P),\chi(G),2)\).