\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{11: More Colorings}{Due Friday, Week 7}



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

\begin{enumerate}
\item When we studied the Mycielski graph construction in class, we left one part of the proof for the homework: namely, the proof that if $G$ is a graph with $\chi(G) = k$ and $G'$ is the result of applying the Mycielski construction to $G$, then $\chi(G') > k$.    Prove this claim!
\item In Wednesday's class, we introduced the idea of a \textbf{block-graph}, which we defined for a given graph $G$ as follows:
\begin{itemize}
\item  A \textbf{block} subgraph $B$ to be any subgraph that is 2-vertex connected and maximal:\ that is, there is no larger subgraph that is two-connected and contains $B$.  
\item We define the \textbf{block graph} $T_G$ of $G$ as follows:
\begin{itemize}
\item Vertices: create one vertex for each block $B_i$ of our graph $G$, and another vertex of our graph for each cut-vertex $x_j$ in our graph.
\item Edges: connect a block $B_i$ to a cut-vertex $x_j$ if and only if $x_j \in B_i$.
\end{itemize}
\end{itemize}
\begin{center}
\includegraphics[height=1.8in]{block_subgraph2.pdf}\\
\footnotesize A graph $G$ along with its ``block-tree'' $T_G$.  \normalsize
\end{center}
Suppose that $G$ is a connected graph and $T_G$ is its block-graph.  Prove the following claims we made about block graphs:
\begin{enumerate}
\item Any two blocks in $G$ share at most one cut-vertex in common.
\item If $e$ is an edge linking two distinct blocks in $G$, then at least one endpoint of $e$ is a cut-vertex.
\item The block-graph $T_G$ is a tree.
\end{enumerate}
\item (This problem was on HW 9, but it had a mistake that made it impossible --- I wrote ``graph'' but wanted ``bipartite graph.''  It's here now!)  A \textbf{vertex cover} of a graph $G$ is a subset of the vertices of $G$ that contains at least one endpoint of every edge.   Prove that for any bipartite graph $G$, the number of vertices in the smallest vertex cover is the same as the number of edges in the largest matching.
\item A graph $G$ is called \textbf{perfect} if $\chi(G) = \omega(G)$. 
\begin{enumerate}
\item Find a graph $G$ that is perfect.  Find another graph $G'$ that is not perfect.
\item Show that if a graph $G$ is bipartite, then its complement $\overline{G}$ is perfect.
\end{enumerate}
\item Suppose that a graph $G$ on $n$ vertices has chromatic number $k$, where $k \geq 3$.  Prove that $G$ contains at most $\frac{n^2 (k-1)!}{k}$ edges.  
\end{enumerate}



\end{document}