\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}
\renewcommand{\emptyset}{\varnothing}

\begin{document}
\headers{Math573}{Homework 7}{Due Tue, Dec. 5, 2017}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 3 of the following 4 problems.  All written work must be your own, using only permitted sources.  See the ``General Guidelines and Advice'' on the homework page for more details.

\begin{enumerate}

\newcommand{\gbox}{\mathbin{\Box}}
\newcommand{\comp}[1]{\overline{#1}}

\item {} Let $G$ be a $k$-colorable graph, and let $P$ be a set of vertices in $G$ such that $\dist(x,y) \ge 4$ whenever $x,y\in P$.  Prove that every coloring of $P$ with colors from $[k+1]$ extends to a proper $(k+1)$-coloring of $G$.

\item {} Prove that if $G$ has no induced $2K_2$, then $\chi(G) \le \binom{\omega(G)+1}{2}$.  (Hint: use a maximum clique to define a collection of $\binom{\omega(G)}{2} + \omega(G)$ independent sets that cover the vertices.)

\item {} Let $G$ be a $k$-chromatic graph with girth $6$ and order $n$.  Construct $G'$ as follows.  Let $T$ be an independent set of $kn$ vertices.  Take $\binom{kn}{n}$ pairwise disjoint copies of $G$, one for each way to choose an $n$-set $S\subset T$.  Add a matching between each copy of $G$ and its corresponding $n$-set $S$.  Prove that the resulting graph has chromatic number $k+1$ and girth $6$.  (Comment: Since $C_6$ has chromatic number $2$ and girth $6$, the process can start and these graphs exist.)

\item {} Let $G$ be a graph with no induced copy of the claw ($K_{1,3}$).
\begin{enumerate}
	\item Show that in a proper coloring, each subgraph of $G$ induced by the union of two color classes consists of paths and even cycles.
	\item An \emph{equitable} coloring of a graph is a proper vertex-coloring in which every pair of color classes differs in size by at most $1$.  Prove that $G$ has an equitable coloring that is optimal (i.e. uses just $\chi(G)$ colors).
\end{enumerate}

\end{enumerate}
\end{document}
