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

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

\begin{document}
\headers{Math573}{Homework 6}{Due Thurs, Dec. 12, 2024}

%\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 5 of the following 6 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{\comp}[1]{\overline{#1}}

\item {} Determine the smallest $m$ such that every $2$-connected graph with $n$ vertices has a $2$-connected spanning subgraph with at most $m$ edges.

\item {} Let $G$ be a graph whose odd cycles are pairwise intersecting, meaning that every two odd cycles in $G$ have a common vertex.  Prove that $\chi(G)\le 5$.

\item {} Let $G$ be a graph not containing a $4$-cycle.  Prove that $\chi(G)\le \alpha'(G) + 2$.

\item {} Let $t$ be a nonnegative integer.  For each $n$ with $n\ge 5t$, construct an $n$-vertex graph with chromatic number $n-2t$ and clique number $n-3t$.

\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}

\item {} Let $G$ be a graph with no induced copy of $P_4$, let $k=\omega(G)$, and let $\sigma$ be an ordering of $V(G)$.  Prove that with respect to $\sigma$, the greedy algorithm produces a proper $k$-coloring of $G$.  Hint: show that if a vertex $u$ receives color $j$, then $u$ completes a $j$-clique with vertices of colors $\{1,2,\ldots,j\}$ that precede $u$ in $\sigma$.


\end{enumerate}
\end{document}
