Two-way-bounding study problems

Problem 1

What is the chromatic number of the following graph? Justify your answer.

solution

Problem 2

(Do problem 1 and check your solution before attempting this problem.)

What is the chromatic number of the following graph? Justify your answer.

solution

Problem 3

Let's define sets A and B as follows:

• \(A = \{(x,y) \in \mathbb{R}^2 : y = 3x + 7\} \)
• \( B = \{\lambda(-2,1) + (1-\lambda)(1,10) : \lambda \in \mathbb{R}\}\)

Prove that A=B.

Hint: this is in the two-way bounding section. What technique do you think we want you to use?

solution

Problem 4

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.

hints

solution