What is the chromatic number of the following graph? Justify your answer.
(Do problem 1 and check your solution before attempting this problem.)
What is the chromatic number of the following graph? Justify your answer.
Let's define sets A and B as follows:
Prove that A=B.
Hint: this is in the two-way bounding section. What technique do you think we want you to use?
Recall that if G is a graph, then \(\chi(G)\) is its chromatic number. Suppose that P is a connected graph and G is another connected graph, not connected to P. Now, create a new graph M which consists of a copy of P, a copy of G, and a new edge that connects some vertex of P to some vertex of G. For example, suppose that P is \(C_5\) and G is \(K_4\). Then M might look as follows, where g marks vertices of G and p marks vertices of P, and the new edge is the dashed line.
Give a formula expressing \(\chi(M)\) in terms of \(\chi(P)\) and \(\chi(G)\)? Be as precise as possible and justify your answer.