%This is a template for typsetting our lecture notes. Please type your
%contribution in a file that can be included to this one using the
% \include command. Please avoid using any complicated macros. If you
%must use any macros or environments not defined here and not recognized
%by this version of LaTeX, please send them separately.
%
%Please use \proof to begin a proof and \qed to end it.
%Please use \boldone or \bo for a bold one to denote a characteristic vector
% or the vector of all ones.
%
\def\date{5 September 2003}
\documentclass[12pt]{article}
\usepackage{amsmath,theorem}
 %%%%%%%%%% BEGIN AUTHOR MACROS %%%%%%%%%%%%%
\def\dfn#1{{\sl #1}}
\def\boldone{{\bf 1}}
\def\bo{{\bf 1}}
\def\proof{{\noindent \bf Proof.~~}}
\def\qed{\hfill$\square$\bigskip\medskip}
\def\sqr#1#2{{\vcenter{\vbox{\hrule height.#2pt
\hbox{\vrule width.#2pt height #1pt \kern#1pt
\vrule width.#2pt}
\hrule height.#2pt}}}}
\def\mytextindent#1{\indent\llap{#1\enspace}\ignorespaces}
\def\fattextindent#1{\indent\indent\llap{#1\enspace}\ignorespaces}
\def\myitem{\par\hangindent\parindent\mytextindent}
\def\square{\mathchoice\sqr56\sqr56\sqr{2.1}3\sqr{1.5}3}
\newtheorem{newthm}{}[section]
{\theorembodyfont{\rmfamily}
\newtheorem{exercise}[newthm]{Exercise}
\newtheorem{definition}[newthm]{Definition}
\newtheorem{observation}[newthm]{Observation}
}  %%% end theorembodyfont
\newtheorem{theorem}[newthm]{Theorem}
\newtheorem{lemma}[newthm]{Lemma}
\newtheorem{corollary}[newthm]{Corollary}
\newtheorem{conjecture}[newthm]{Conjecture}
\def\JCTB{J.\ Combin.\ Theory Ser.\ B}
\def\CMUC{Comment.\ Math.\ Univ.\ Carol.}
\def\TAMS{Trans.\ Amer.\ Math.\ Soc.}
\def\DM{Discrete Math.}
\def\CM{Contemporary Math.}
\def\GC{Graphs and Combin.}
\def\COM{Combinatorica}
\def\JGT{J.\ Graph Theory}
\def\JAMS{{\it J.~Amer.\ Math.\ Soc.}}

%%%%%%%%%   END AUTHOR MACROS %%%%%%%%%%%%%

\begin{document}
\phantom{a}\vskip .25in
\centerline{{\bf LECTURES ON PERFECT GRAPHS}}
\vskip.5in
\bigskip
\centerline{Lectures by}
\centerline{\bf Robin Thomas}
\centerline{written down by his students}
\vskip.5in
A graph is \dfn{perfect} if for every induced subgraph, the chromatic number
is equal to the maximum size of a complete subgraph.
Perfect graphs appear naturally in a variety of circumstances, such as
communication complexity, integrality of polyhedra, polyhedral
combinatorics, the channel assignment problem, the geometric algorithms
of Gr\"otschel, Lov\'asz and Schrijver, or semi-definite programming.
They are also the source of fundamental mathematical problems.

The course will cover classical topics in perfect graph theory, and will go
through selected portions of the recent proof of the Strong Perfect Graph
Conjecture, with emphasis on open problems and areas for future research.

\vfill
\noindent 2 September 2003.
Revised \date.
\hfil\break\noindent %This is a draft subject to a future revision.
\vfil\eject
%End of title page
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}\label{sec:intro}

Graphs are finite and simple; that is, they have no
loops or multiple edges.
Let $G$ be a graph.
A \dfn{hole} in $G$ is an induced cycle of length at least four.
An \dfn{antihole} in $G$ is an induced subgraph isomorphic to
the complement of a hole.
(The {\sl complement} of a graph $G$ is the graph with vertex-set $V(G)$
and edge-set consisting precisely of all distinct pairs of vertices
that are not adjacent in $G$.)
A \dfn{clique} in $G$ is a set $X\subseteq V(G)$ of pairwise adjacent
vertices, and a \dfn{stable set} is a set 
of pairwise non-adjacent vertices. The size of a maximum clique of a graph $G$
is denoted by $\omega(G)$ and the size of a maximum stable set is denoted
by $\alpha(G)$. The \dfn{chromatic number} of $G$, denoted by $\chi(G)$,
is the least number of colors needed to color the vertices of $G$ in
such a way that adjacent vertices receive different colors.
In other words, $\chi(G)$ is the minimum number $k$ such that the vertex-set
$V(G)$ of $G$ can be partitioned into $k$ stable sets.
Clearly $\chi(G)\ge\omega(G)$ for every graph $G$, but equality need not
hold. For instance, if $G$ is an odd hole (i.e., a hole with an odd number
of vertices), then $\chi(G)=3>2=\omega(G)$.
Similarly, if $G$ is an odd antihole, say on $2k+1$ vertices, then
 $\chi(G)=k+1>k=\omega(G)$.

A graph
$G$ is \dfn{perfect} if $\chi(H)=\omega(H)$ for every induced subgraph $H$ of $G$;
that is,
the chromatic number of $H$ is equal to the maximum size of a clique
of $H$. Thus odd holes and odd antiholes are not perfect, and neither is
any other graph that has an odd hole or an odd hole antihole.
Are there any other imperfect graphs? Berge \cite{BerSPGC} conjectured
in 1961 that there are not, and a proof of that will be discussed later.

\begin{newthm}\label{spgc} A graph is perfect if and only if it
has no odd hole and no odd antihole.
\end{newthm}


We will begin by discussing the relevance of perfect graphs.
We refer the reader to the excellent book by Ram\'\i{r}ez Alfons\'\i{n}
and Reed \cite{RamRee} for further reading.

\end{document}
