\documentclass[letterpaper,12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
\usepackage{palatino}
\usepackage{latexsym,amssymb,amsfonts,amsmath}
\usepackage{amsthm}
\usepackage{verbatim}
\usepackage{paralist}
\usepackage{graphics}
\usepackage[all]{xy}
\pagestyle{empty}

\addtolength{\voffset}{-2cm}
\addtolength{\textheight}{3cm}
\addtolength{\textwidth}{1.5cm}
\addtolength{\hoffset}{-0.5cm}
% \addtolength{\textwidth}{2cm}

\newcommand{\header}[2]{
	\begin{center}
 		\rule{\linewidth}{1pt}
 		\Large{#1}
 		\rule{\linewidth}{1pt}
 		\normalsize{#2}
 	\end{center}
}

\theoremstyle{plain}
\newtheorem{proposicion}{Proposition}
\newtheorem{lema}{Lema}
\newtheorem{teorema}{Teorema}
\newtheorem{corolario}{Corolario}
\newtheorem{conjetura}{Conjetura}

\theoremstyle{definition}
\newtheorem{definicion}[proposicion]{Definición}

\renewcommand{\figurename}{Figura}

\DeclareMathOperator{\mcd}{mcd}
\DeclareMathOperator{\exc}{e}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\cc}{cc}
\DeclareMathOperator{\Q}{Q}
\DeclareMathOperator{\domatic}{d}

\begin{document}
\header{Teoría de las Gráficas II}{Quinta tarea}
Se entrega el viernes 16 de abril. Todos los ejercicios bien justificados.
\vspace{0.5cm}
\begin{enumerate}
\item Describe todas las gráficas con $\chi'(G)\leq 2$.
\item ¿Las siguientes ecuaciones son verdaderas?
\begin{displaymath}
 \chi(G)=\chi'(L(G))\text{,}\qquad \chi'(G)=\chi(L(G))\text{.}
\end{displaymath}
\item Muestra que $\chi'(K_{m,n})=\Delta(K_{m,n})$ exhibiendo una coloración apropiada.
\item Considera $G$ una gráfica que no sea un ciclo dirigido de longitud impar. Prueba que $\chi'(G)=\Delta(G)$ si todos los ciclos de $G$ tienen la misma paridad.
\item Prueba que $\chi'(G)=\Delta(G)+1$ para gráficas regulares de orden impar y con al menos una arista.
\item Una gráfica se dice \emph{isocromática} si $\chi(G)=\chi'(G)$. Encuentra todas las gráficas isocromáticas entre las gráficas completas y las bipartitas.
\item Encuentra una gráfica cúbica $G$ de orden mínimo con $\chi'(G)=4$.
\item Diremos que una gráfica $G$ es de \emph{clase 1} si $\chi'(G)=\Delta(G)$ y de \emph{clase 2} si $\chi'(G)=\Delta(G)+1$. Una gráfica es \emph{$\chi'$-crítica} si es conexa, es de clase 2 y al borrar cualquier arista disminuye su índice cromático.
 \begin{enumerate}
 \item Construye una gráfica $\chi'$-crítica $G$ de orden cinco con $\Delta(G)=3$.
 \item ¿Para qué valores de $n$ se tiene que $K_n$ es $\chi'$-crítica?
 \item Prueba que no existe gráficas $\chi'$-críticas de orden cuatro o seis con $\Delta(G)=3$.
 \end{enumerate}
\item Considera una gráfica $G$ con $2n+1$ vértices y más de $n\Delta(G)$ aristas. Entonces $\chi'(G)=\Delta+1$.
\item Muestra que toda gráfica cúbica hamiltoniana tiene índice cromático tres.
\item Considera $G:=C[\overline{K_2}]$.
 \begin{enumerate}
 \item Si $M$ y $M'$ son dos apareamientos perfectos distintos de $G$, muestra que existe un automorfismo que se lleva a uno en el otro.
 \item Deduce que $\chi'(G)=4$.
 \item Más aún, deduce que $G$ no contiene a Petersen.
 \end{enumerate}
\item Considera $G$ una gráfica de tamaño $m$ y $\alpha'$ el número de independencia en aristas. Si $m > \Delta(G)\alpha'(G)$ entonces $G$ es de clase 2.
\end{enumerate}
\end{document}