\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{10: Colorings}{Due Friday, Week 6}



Do \textbf{one} of the three problems listed here!  Have fun, prove all of your claims, and let me know if you have any questions!  

\begin{enumerate}
\item We define an \textbf{independent set} of vertices in a graph $G$ as any collection of vertices from $G$ that have no edges linking them, and the \textbf{independence number} $\alpha(G)$ of a graph $G$ as the largest independent set contained within $G$.  For example, 
\begin{center}
\includegraphics[height=.7in]{independence_ex.pdf}
\end{center}
is a graph with $\alpha(G) = 4$ (with an independent set of four vertices drawn in yellow.)  
\begin{enumerate}
\item Prove that $\alpha(G) = 4$ for the example graph above (i.e.\ explain why no subset of five vertices here could be an independent set.)
\item Take any graph $G$.  Prove that $\frac{|V(G)|}{\alpha(G)} \leq \chi(G)$.
\end{enumerate}
\item On homework set 5, problem 5, we proved that $\chi(G) \leq \Delta(G) + 1$, and did so using a concept called the \textbf{greedy} algorithm.  (We will review this in class on Wednesday, as well, in case you forgot how it works.)  

However, for some graphs, this bound is very weak.  For example, if you consider the \textbf{complete bipartite graph} $K_{n,n}$ formed by taking two groups of $n$ vertices and connecting all vertices in one group to the other group, the degree of any vertex in this graph is $n$, while the chromatic number is 2.  
\begin{enumerate}
\item Prove that the greedy algorithm can ``fail'' you in the way suggested by this bound.  Specifically: find a graph $G$ and an ordering of $G$'s vertices so that if we run the greedy algorithm using this ordering, we come up with a coloring of our graph that is not the best possible.
\item Conversely: show that for any graph $G$, there is \textbf{some} enumeration $(v_1, \ldots v_n)$ of $V(G)$ such that using the greedy algorithm to color $G$'s vertices uses \textbf{exactly} $\chi(G)$ colors.  (This is the converse to part (a) here:\ in that part, you proved that it is \textbf{possible} for the greedy algorithm to mess up, while in this problem you're proving that it is also possible that the greedy algorithm does \textbf{not} mess up!)
\end{enumerate}
\item  In class on Tuesday, we described the Mycielski process, that takes in a triangle-free graph with chromatic number $k$ and outputs a triangle-free graph with chromatic number $k+1$.  The following problem is a stronger process: it aims to take in a graph with chromatic number $k$ that do not contain any $C_3, C_4$, or $C_5$'s, and output a graph with chromatic number $k+1$ that still does not contain any $C_3, C_4$, or $C_5$'s.

We do this as follows:  Let $G$ be a $k$-chromatic graph with no cycles of length 5 or  smaller, with vertex set $\{v_1,\ldots v_n\}$.  Construct a new graph $G'$ as follows:
\begin{itemize}
\item Let $T$ be a set of $kn$ vertices, $\{t_1, \ldots t_{kn}\}$ with no edges between them.  
\item Take $\binom{kn}{n}$ disjoint copies of $G$, one for every $n$-subset of $\{1, \ldots kn\}$ and index them by these subsets: i.e. for any subset $\{i_1, \ldots i_n\} \subseteq \{1, \ldots kn\}$, make a subgraph $G_{\{i_1, \ldots i_n\}}$.
\item Take each $G_{\{i_1, \ldots i_n\}}$, and connect the vertices of $G$ to the corresponding vertices in $T$ given by $G$'s indexing subset.  In other words, throw in the edges $\{v_1, t_{i_1}\}, \{v_2, t_{i_2}\}, \ldots \{v_n, t_{i_n}\}$ to our graph made by the the $G$'s and the set $T$.
\end{itemize}
Show that this graph still has girth $\geq 6$, as well as chromatic number greater than $ \chi(G)$.
\end{enumerate}



\end{document}