1.
We proceed by induction on \(t\text{.}\) For \(t=3\text{,}\) we take \(\bfG_{3}\) to be the cycle \(\bfC_{5}\) on five vertices. (Why is \(\chi(\bfG_{3})=3\text{?}\) Why is \(\omega(\bfG_{3})=2\text{?}\))
Print preview
Worksheet 5.2 Graphs with \(\omega(\bfG)=2\) and \(\chi(\bfG)\) large
We’ve already seen that the chromatic number \(\chi(\bfG)\) of a graph \(\bfG\) is at least its clique number \(\omega(\bfG)\text{.}\) (Recall that if \(\omega(\bfG)=t\text{,}\) then \(\bfG\) contains a subgraph isomorphic to \(\bfK_{t}\) and \(\chi(\bfK_{t})=t\text{.}\)) In this activity, we’re going to see how to construct graphs with \(\omega(\bfG)=2\) and \(\chi(\bfG)=t\) for any integer \(t\geq 2\text{.}\) We will focus only on the construction of Mycielski, which is one of two constructions included in the text.
This construction aims to create a graph \(\bfG_{t}\) with \(\chi(\bfG_t)=t\) and \(\omega(\bfG_{t})=2\text{.}\) The construction is inductive. It starts by creating \(\bfG_{3}\text{,}\) then uses that to make \(\bfG_{4}\text{,}\) which it uses to make \(\bfG_{5}\text{,}\) etc. As you go through, discuss the steps with your group members. The questions in italics are questions you must be able to answer to ensure you understand as you go through things.
2.
Now assume that for some \(t\ge3\text{,}\) we have determined the graph \(\bfG_{t}\text{.}\) Suppose that \(\bfG_{t}\) has \(n_{t}\) vertices. Label the vertices of \(\bfG_{t}\) as \(x_{1},x_{2},\dots,x_{n_t}\text{.}\) Construct \(\bfG_{t+1}\) as follows.
-
Add a copy of \(\bfG_{t}\) with \(y_{i}\) adjacent to \(x_{j}\) if and only if \(x_{i}\) is adjacent to \(x_{j}\text{.}\)
-
Attach a new vertex \(z\) adjacent to all vertices in \(I\) (but none from the copy of \(\bfG_{t}\)).
How many vertices does \(\bfG_{t+1}\) contain? (Your formula will contain \(n_{t}\text{.}\)) You should be able to draw \(\bfG_{4}\) by hand, and \(\bfG_{5}\) will have \(23\) vertices.
3. \(\omega(\bfG_{t+1})=2\).
To see that \(\omega(\bfG_{t+1})=2\text{,}\) it will suffice to argue that \(\bfG_{t+1}\) contains no triangle (\(\bfK_{3}\)). To do this, we consider where the vertices of a triangle would be:
(a)
(b)
(c)
(d)
A triangle must thus contain a vertex \(y_{i}\in I\) and vertices \(x_{j}\) and \(x_{k}\) from the copy of \(\bfG_{t}\text{.}\) Explain why \(\{y_{i},x_{j},x_{k}\}\) forming a triangle mean that there’s a triangle in \(\bfG_{t}\text{.}\)
4. \(\chi(\bfG_{t+1})=t+1\).
(a)
What part of the construction ensures that \(\chi(\bfG_{t+1})\ge t\text{?}\)
(b)
How can you color the vertices of \(I\) using \(t\) colors? (Hint: Pair vertices of \(I\) with vertices of \(\bfG_{t}\text{.}\)) What color does \(z\) get? How many colors have you used and what does this say about \(\chi(\bfG_{t+1})\text{?}\)
(c)
Try coloring \(\bfG_{t+1}\) using only \(t\) colors. Suppose that \(\phi\) is a proper coloring of \(\bfG_{t+1}\) using the colors \(\{1,2,\dots,t\}\text{.}\) It’s safe to assume that \(\phi(z) = t\) (reshuffle the colors otherwise). Let \(S\) be the set of vertices in the copy of \(\bfG_{t}\) to which \(\phi\) assigns color \(t\text{.}\) Can the set \(S\) be empty? Explain your reasoning.
(d)
Since \(\phi(z)=t\text{,}\) what do you know about the set (or even number) of colors used on \(I\text{?}\)
(e)
Why can you change the color of each \(x_{i}\in S\) to match the color \(\phi\) assigns to \(y_{i}\) and maintain a proper coloring?
(f)
Now how many colors have you used on the copy of \(\bfG_{t}\text{?}\)
