Applied Combinatorics

Let \(\GVE\) be a \(2\)-colorable graph whose coloring function partitions \(V\) as \(A\cup B\text{.}\) Since there are no edges between vertices on the same side of the partition, any cycle in \(\bfG\) must alternate vertices between \(A\) and \(B\text{.}\) In order to complete the cycle, therefore, the number of vertices in the cycle from \(A\) must be the same as the number from \(B\text{,}\) implying that the cycle has even length.

We proceed by induction on \(t\text{.}\) For \(t=3\text{,}\) we take \(\bfG_3\) to be the cycle \(\bfC_5\) on five vertices. 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. Begin with an independent set \(I\) of cardinality \(t(n_t-1)+1\text{.}\) For every subset \(S\) of \(I\) with \(|S|=n_t\text{,}\) label the elements of \(S\) as \(y_1,y_2,\dots,y_{n_t}\text{.}\) For this particular \(n_t\)-element subset attach a copy of \(\bfG_t\) with \(y_i\) adjacent to \(x_i\) for \(i=1,2,\dots,n_t\text{.}\) Vertices in copies of \(\bfG_t\) for distinct \(n_t\)-element subsets of \(I\) are nonadjacent, and a vertex in \(I\) has at most one neighbor in a particular copy of \(\bfG_t\text{.}\)

To see that \(\omega(\bfG_{t+1})=2\text{,}\) it will suffice to argue that \(\bfG_{t+1}\) contains no triangle (\(\bfK_3\)). Since \(\bfG_t\) is triangle-free, any triangle in \(\bfG_{t+1}\) must contain a vertex of \(I\text{.}\) Since none of the vertices of \(I\) are adjacent, any triangle in \(\bfG_{t+1}\) contains only one point of \(I\text{.}\) Since each vertex of \(I\) is adjacent to at most one vertex of any fixed copy of \(\bfG_t\text{,}\) if \(y\in I\) is part of a triangle, the other two vertices must come from distinct copies of \(\bfG_t\text{.}\) However, vertices in different copies of \(\bfG_t\) are not adjacent, so \(\omega(\bfG_{t+1})=2\text{.}\) Notice that \(\chi(\bfG_{t+1})\ge t\) since \(\bfG_{t+1}\) contains \(\bfG_t\text{.}\) On the other hand, \(\chi(\bfG_{t+1})\le t+1\) since we may use \(t\) colors on the copies of \(\bfG_t\) and a new color on the independent set \(I\text{.}\) To see that \(\chi(\bfG_{t+1})=t+1\text{,}\) observe that if we use only \(t\) colors, then by the generalized Pigeon Hole Principle, there is an \(n_t\)-element subset of \(I\) in which all vertices have the same color. Then this color cannot be used in the copy of \(\bfG_t\) which is attached to that \(n_t\)-element subset.

We again start with \(\bfG_3\) as the cycle \(\bfC_5\text{.}\) As before we assume that we have constructed for some \(t\ge3\) a graph \(\bfG_t\) with \(\omega(\bfG_t)=2\) and \(\chi(\bfG_t) = t\text{.}\) Again, label the vertices of \(\bfG_t\) as \(x_1,x_2,\dots,x_{n_t}\text{.}\) To construct \(\bfG_{t+1}\text{,}\) we now start with an independent set \(I\text{,}\) but now \(I\) has only \(n_t\) points, which we label as \(y_1,y_2,\dots,y_{n_t}\text{.}\) We then 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{.}\) Finally, attach a new vertex \(z\) adjacent to all vertices in \(I\text{.}\)

Clearly, \(\omega(\bfG_{t+1})=2\text{.}\) Also, \(\chi(\bfG_{t+1})\ge t\text{,}\) since it contains \(\bfG_t\) as a subgraph. Furthermore, \(\chi(\bfG_{t+1})\leq t+1\text{,}\) since we can color \(\bfG_t\) with colors from \(\{1,2,\dots,t\}\text{,}\) use color \(t+1\) on the independent set \(I\text{,}\) and then assign color \(1\) to the new vertex \(z\text{.}\) We claim that in fact \(\chi(\bfG_{t+1})=t+1\text{.}\) Suppose not. Then we must have \(\chi(\bfG_{t+1})=t\text{.}\) Let \(\phi\) be a proper coloring of \(\bfG_{t+1}\text{.}\) Without loss of generality, \(\phi\) uses the colors in \(\{1,2,\dots,t\}\) and \(\phi\) assigns color \(t\) to \(z\text{.}\) Then consider the nonempty set \(S\) of vertices in the copy of \(\bfG_t\) to which \(\phi\) assigns color \(t\text{.}\) For each \(x_i\) in \(S\text{,}\) change the color on \(x_i\) so that it matches the color assigned to \(y_i\) by \(\phi\text{,}\) which cannot be \(t\text{,}\) as \(z\) is colored \(t\text{.}\) What results is a proper coloring of the copy of \(\bfG_t\) with only \(t-1\) colors since \(x_i\) and \(y_i\) are adjacent to the same vertices of the copy of \(\bfG_t\text{.}\) The contradiction shows that \(\chi(\bfG_{t+1})=t+1\text{,}\) as claimed.

For each \(v\in V\text{,}\) let \(I(v)=[a_v,b_v]\) be a closed interval of the real line so that \(uv\) is an edge in \(\bfG\) if and only if \(I(u)\cap I(v)\neq\emptyset\text{.}\) Order the vertex set \(V\) as \(\{v_1,v_2,\dots v_n\}\) such that \(a_1\leq a_2\leq \cdots \leq a_n\text{.}\) (Ties may be broken arbitrarily.) Apply the First Fit coloring algorithm to \(\bfG\) with this ordering on \(V\text{.}\) Now when the First Fit coloring algorithm colors \(v_i\text{,}\) all of its neighbors have left end point at most \(a_i\text{.}\) Since they are neighbors of \(v_i\text{,}\) however, we know that their right endpoints are all at least \(a_i\text{.}\) Thus, \(v_i\) and its previously-colored neighbors form a clique. Hence, \(v_i\) is adjacent to at most \(\omega(\bfG)-1\) other vertices that have already been colored, so when the algorithm colors \(v_i\text{,}\) there will be a color from \(\{1,2,\dots,\omega(\bfG)\}\) not already in use on its neighbors. The algorithm will assign \(v_i\) the smallest such color. Thus, we never need to use more than \(\omega(\bfG)\) colors, so \(\chi(\bfG)=\omega(\bfG)\text{.}\)