\documentstyle[fullpage]{article}
\pagestyle{plain}
\newcommand{\bd}{\begin{displaymath}}
\newcommand{\ed}{\end{displaymath}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\bt}{\begin{tabbing}}
\newcommand{\et}{\end{tabbing}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\bs}{\bigskip}
\newcommand{\noi}{\noindent}
\newcommand{\bsnoi}{\bigskip\noindent}
\newcommand{\eps}{\varepsilon}
\newcommand{\la}{\leftarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\begin{document}
\bc
{\Large\bf PROBLEMS CONCERNING PERFECT GRAPHS}
\ec
\bs
This draft includes additions by Claude Berge, Leizhen Cai, Guoli
Ding, Vladimir Gurvich, Andr\'as Gy\'arf\'as, Alain Hertz, Stefan
Hougardy, Fr\'ed\'eric Maire, Fr\'ed\'eric Maffray,
K.~R.~Parthasarathy, Myriam Preissmann, G.~Ravindra, Bruce Reed, Irena
Rusu, Andr\'as Seb\H o, R.Sritharan, Zsolt Tuza, and myself. Please,
send
\bi
\item[(i)] your additions to the list,
\item[(ii)] information on partial (or better yet, complete) progress
towards solving these problems, and
\item[(iii)] complaints in case we did not give credit where credit
was due
\ei
by e-mail to
\begin{center}
{\tt chvatal@dimacs.rutgers.edu}
\end{center}
or by ordinary mail to
\begin{center}
Va\v{s}ek Chv\'atal, Dept.Computer Science, Rutgers University,\\
New Brunswick, NJ 08903, USA.
\end{center}
\bs
\bc
{\large\bf 1. BERGE GRAPHS: BUILDING BLOCKS AND STRUCTURAL FAULTS?}\\
\ec
\bc
***
\ec
A {\em hole} in a graph is an induced subgraph isomorphic to a cycle
of length at least four; an {\em antihole} is an induced subgraph
isomorphic to the complement of such a cycle; holes and antiholes are
{\em odd} or {\em even} according to the parity of their number of
vertices. A graph is called {\em Berge} if it contains no odd hole
and no odd antihole. In this terminology, the Strong Perfect Graph
Conjecture asserts that a graph is perfect if (and only if) it is
Berge. A {\em monster} (term suggested by Pierre Duchet) is a minimal
imperfect graph which is Berge.
\bc
***
\ec
A graph is called {\em $F$-free} if it contains no induced subgraph
isomorphic to $F$; the {\em diamond} is the graph with four vertices
and five edges; Parthasarthy and Ravindra \cite{PR} and Tucker
\cite{T87} proved that diamond-free Berge graphs are perfect.
A {\em star-cutset} in a graph $G$ is nonempty set $C$ of vertices
such that $G-C$ is disconnected and such that some vertex in $C$ is
adjacent to all the remaining vertices in $C$; a {\em stable cutset}
is a stable set $S$ such that $G-S$ is disconnected; an {\em even
pair} is a pair of vertices such that every chordless path between
them has an even number of edges. Chv\'atal \cite{C85} proved that no
minimal imperfect graph contains a star-cutset; Tucker \cite{T83}
proved that no monster has a stable cutset; Fonlupt and Uhry \cite{FU}
and later Meyniel \cite{M87} proved that no minimal imperfect graph
contains an even pair.
Hence the following conjecture implies the Strong
Perfect Graph Conjecture.\\
{\sc Conjecture:} {\em If $G$ is a Berge graph such that
\hspace{1.5in} neither $G$ nor $\overline{G}$ has a star-cutset,
\hspace{1.5in} neither $G$ nor $\overline{G}$ has a stable cutset, and
\hspace{1.5in} neither $G$ nor $\overline{G}$ contains an even pair,
\hspace{1.1in} then $G$ or $\overline{G}$ is diamond-free.}\\
\noindent The assumption that neither $G$ nor $\overline{G}$ contains
an even pair cannot be dropped: consider the (self-complementary)
graph with vertices $a,b, \ldots ,h$ and edges
$ab,ac,ad,bc,cd,ef,eg,eh,fg,fh,ae,bf,cg,dh$. Stefan Hougardy
\cite{Hou} found a counterexample to a related stronger conjecture
(with the assumption that neither $G$ nor $\overline{G}$ has a stable
cutset dropped and ``diamond-free'' replaced by ``the line-graph of a
bipartite graph'') .\\
{\tt RESOLVED: Irena Rusu constructed the following counterexample.
Substitute the complete graph with vertices $u_i,v_i$ for each $w_i$
in the cycle with vertices $w_1,w_2, \ldots ,w_6$ and edges\\ $w_1w_2,
w_2w_3, \ldots ,w_6w_1$; for each $i=1,2,3$, add vertices $x_i,y_i$
and edges $x_iy_i,\ x_iu_i, x_iu_{i+3}, u_iu_{i+3},$\\ $y_iv_i,
y_iv_{i+3}, v_iv_{i+3}.$}\\
\bc
{\large\bf 2. SPECIAL CLASSES OF BERGE GRAPHS}\\
\ec
\bc
***
\ec
A graph is called {\em Raspail} or {\em short-chorded} if each of its
cycles whose length is odd and at least five has a ``short chord'',
meaning a chord that along with two edges of the cycle forms a
triangle.
A {\em neighborhood subgraph} is the subgraph induced by some vertex
and all its neighbors; the {\em neighborhood number} is the smallest
number of neighborhood subgraphs whose union covers all the edges of
the graph; the {\em neighborhood independence number} is the largest
number of edges, no two of which belong to the same neighborhood
subgraph; a graph is called {\em neighborhood-perfect} if, for each of
its induced subgraphs $F$, the neighborhood number of $F$ is equal to
the neighborhood independence number of $F$. Neighborhood-perfect
graphs were introduced in \cite{LT} (see also \cite{CFT}).
An {\em opposition graph} is a graph admitting an
orientation which puts the two wings of every induced $P_4$ in
opposition: if the $P_4$ has vertices $a,b,c,d$ and edges $ab,bc,cd$
then $a \ra b, d \ra c$ or $b \ra a, c \ra d$.
{\em Ho\`{a}ng graphs} are graphs whose edges can be colored red and
white in such a way that the two wings of every induced $P_4$ have
different colors; the ``wings'' of a $P_4$ with vertices $a,b,c,d$ and
edges $ab,bc,cd$ are $ab$ and $cd$. Ho\`ang graphs were introduced in
\cite{Hoa}.
A {\em kernel} in a directed graph is a stable set $S$ such that for
every vertex $x$ outside $S$ there is an arc $x \ra y$ with $y$ in
$S$. Clearly, an orientation (with pairs of parallel arcs in opposite
directions allowed) of a complete graph has no kernel if and only if
it has no sink; clearly, this is the case if and only if there is a
directed hamiltonian circuit with no arc complemented by a parallel
arc in the opposite direction; such an orientation of a complete graph
will be called a {\em whirl} . A graph is called {\em nearly-perfect}
if every whirl-free orientation of this graph has a kernel.
Nearly perfect graphs were introduced by Berge and Duchet in 1983:
see \cite{BD2},\cite{BD3}.
\bc
***
\ec
\noi Prove that the following classes of graphs include no imperfect
graphs:
\bi
\item[(i)] square-free Berge graphs (``square''=$C_4$),
\item[(ii)] gem-free Berge graphs (``gem''= graph with vertices
$a,b,c,d,x$ and edges $ab,bc,cd,xa,xb,xc,xd$),
\item[(iii)] short-chorded graphs,
\item[(iv)] neighborhood-perfect graphs,
\item[(v)] opposition graphs,
\item[(vi)] Ho\`{a}ng graphs,
\ei
For partial results towards (iii), see \cite{Lu} and \cite{Su};
for a partial result towards (v), see \cite {O}.\\
\bi
\item[(vii)] {\sc Conjecture} (Berge and Duchet): A graph is perfect
if and only if it is nearly-perfect.
\ei
For partial results towards (vii), see
\cite{Bli},\cite{BD2},\cite{BD3},\cite{BDM},\cite{Ma},\cite{BE}.\\
\bsnoi Design polynomial-time algorithms to recognize the following
classes of graphs\\
(or prove that the recognition problem is ${\cal NP}$-complete):
\bi
\item[(viii)] square-free Berge graphs,
\item[(ix)] gem-free Berge graphs,
\item[(x)] short-chorded graphs,
\item[(xi)] neighborhood-perfect graphs.
\item[(xii)] $K_4$-free Berge graphs,
\ei
\bs
\bc
***
\ec
The following problems were contributed by Leizhen Cai.
\bi
\item[(xiii)] Does the Strong Perfect Graph Conjecture hold for
line-graphs of $k$-uniform hypergraphs?
\ei
A {\em $K_{i+1}$-free $k$-colouring} of a graph $G$ is a partition of
the vertex-set of $G$ into $k$ classes, each of which induces a
$K_{i+1}$-free subgraph of $G$; the {\em $i$-chromatic number} of $G$
is the least integer $k$ for which $G$ has a $K_{i+1}$-free
$k$-colouring; the {\em $i$-clique number} of $G$ is $\lceil
\omega(G)/i \rceil$; a graph $G$ is {\em $i$-perfect} if (and only
if), for each induced subgraph $H$ of $G$, the $i$-chromatic number of
$H$ equals the $i$-clique number of $H$.
\bi
\item[(xiv)] (Cai and Corneil \cite{CC}) Does the Strong Perfect Graph
Conjecture hold for 2-perfect graphs?
\ei
The {\em neighborhood clique number} of a graph is the largest number
of edges in any neighborhood subgraph of the graph; the {\em
neighborhood chromatic index} is the least number of colours required
to colour all the edges of the graph so that all edges in any
neighborhood subgraph have distinct colours. A graph is {\em
neighborhood $\chi$-perfect} if (and only if), for each induced
subgraph $H$ of $G$, the neighborhood clique number of $H$ equals the
neighborhood chromatic index of $H$. (Neighborhood $\chi$-perfect
graphs are not necessarily perfect.)
\bi
\item[(xv)] Characterize neighborhood $\chi$-perfect graphs.
\item[(xvi)] Is there a class ${\cal C}$ of perfect graphs such that
(a) ${\cal C}$ does not include all perfect graphs and \\ (b) every
perfect graph contains a vertex whose neighbors induce a subgraph that
belongs to ${\cal C}$?
\ei
\newpage
\bc
{\large\bf 3. DECOMPOSITIONS}\\
\ec
One neat paradigm is this: If the vertices of a graph $G$ can be
colored red and white in such a way that certain conditions are
satisfied then $G$ is perfect if and only if each of its two subgraphs
induced by all the vertices of the same color is perfect. An example
is the theorem of Chv\'atal \cite{C87} on ``partner decompositions''. Here, the
condition is that every two partners have the same color; vertices
$x$ and $y$ are called partners if, and only if, there is a set $S$
of vertices such that both $S \cup \{ x \}$ and $S \cup \{ y \}$
induce a $P_4$.
Chv\'atal, Lenhart, and Sbihi \cite{CLS} investigated this paradigm
with the conditions specialized to forbidding certain types of induced
$P_4$s: a $P_4$ with vertices $a,b,c,d$ and edges $ab,bc,cd$ is of
type RRWR if $a,b,d$ are red and $c$ is white (other types are defined
similarly). They found six cases where the paradigm holds (and showed
that, in a sense, this list of six is complete):
\bi
\item[1.] Forbid types WRRR,RWRR,RWWW,WRWW.
\item[2.] Forbid types RRRR,RWWR,WRRW,WWWW.
\item[3.] Forbid types WRRR,RWRR,RWWR,WRRW,WWWW.
\item[4.] Forbid types WRRR,RWRW,RWWR,WRRW,WWWW.
\item[5.] Forbid types WRRR,RWRW,RWWR,WRRW,RWWW.
\item[6.] Forbid types WRRR,WRRW,WRWW.
\ei
(The first of these cases is an earlier theorem of Chv\'atal and
Ho\`{a}ng \cite{CH}; Case 2 was rediscovered independently by Gurvich
\cite{Gu92}.)
In each of these six cases, given a graph $G$, can you find in
polynomial time a coloring satisfying the condition of this case (with
at least one vertex red and at least one vertex white) or prove that
such a coloring does not exist? In Case 1, the answer is ``yes'': the
task reduces to the problem of deciding whether a system of linear
congruences mod 2 has a non-constant solution. What are the answers in
the remaining five cases? Even if the problem of recognizing graphs
that can be colored to satisfy the condition of, say, Case 6 turned
out to be ${\cal NP}$-complete, there would still be hope for progress:
it is conceivable that the condition of Case 6 can be relaxed to yield
a stronger theorem, and that the relaxed condition can be tested in
polynomial time.
\bs
Case 2 is a little special: here, neither of two subgraphs induced by
all the vertices of the same color contains an induced $P_4$, and so
(by a theorem of Seinsche \cite{Se}) each of these two subgraphs
is perfect. Hence a stronger statement holds true:\\
If the vertices of a graph $G$ can be
colored red and white in such a way that
there is no induced $P_4$ of type RRRR,RWWR,WRRW, or WWWW
then $G$ is perfect.
\bsnoi Gurvich \cite{Gu93} strengthened this statement further as follows:\\
If the vertices of a graph $G$ can be
colored red and white in such a way that
there is no induced $P_4$ of type RRRR or WWWW and
each $P_4$ of type RWWR or WRRW is ``innocuous''
then $G$ is perfect.
\bsnoi Here, a $P_4$ of type RWWR (resp. WRRW) with vertices
$a,b,c,d$ and edges $ab,bc,cd$ is said to be innocuous if $a$ and $d$
belong to different components of the graph induced by all the red
(resp. white) vertices and if $b$ and $c$ belong to different
components of the complement of the graph induced by all the white
(resp. red) vertices.
\bs
\newpage
\bc
{\large\bf 4. PARTITIONABLE GRAPHS, MINIMAL IMPERFECT GRAPHS,\\
AND MONSTERS}\\
\ec
\bc
***
\ec
Following Bland, Huang, and Trotter \cite{BHT}, let us call a graph
{\em partitionable} if, for some $\alpha$ and $\omega$, it has $\alpha
\omega +1$ vertices and, no matter which vertex is removed, the set of
the remaining $\alpha \omega $ vertices can be partitioned into
$\alpha$ pairwise disjoint cliques of size $\omega$ and also into
$\omega$ pairwise disjoint stable sets of size $\alpha$. Lov\'asz
\cite{L1} proved that every minimal imperfect graph is partitionable.
A {\em skew partition} of a graph $G$ is a partition of the vertex-set
of $G$ into disjoint sets $A$ and $B$ such that $A$ induces a
disconnected subgraph of $G$ and $B$ induces a disconnected subgraph
of the complement of $G$. A {\em small transversal\/} in a
partitionable graph is a set of $\alpha +\omega -1$ vertices which
meets all cliques of size $\omega$ and all stable sets of size
$\alpha$; Chv\'atal \cite{C84} pointed out that no minimal imperfect
graph contains a small transversal.
\bc
***
\ec
Prove that every minimal imperfect graph $G$ with $n$ vertices has the
following properties:
\bi
\item[(i)] $G$ admits no skew partition\\
(this problem comes from Chv\'atal \cite {C85}),
\item[(ii)]
[David Avis] min$\{\alpha(G), \omega(G) \} = o(n^{1/2})$,
\item[(iii)] [K.R.Parthasarathy, G.Ravindra] if $G$ is
self-complementary then $G=C_5$,
\item[(iv)] [G.Ravindra] if $v$ is a vertex of degree $2\omega -2$
then the neighborhood of $v$ does not contain three pairwise
nonadjacent vertices,
\item[(v)] if $G \neq C_5$ then every $P_4$ in $G$ extends into a $P_5$ or a $\overline{P_5}$.
\ei
Possibly
every {\em partitionable} graph has property (v).
\bi
\item[(vi)] Design a polynomial-time algorithms to recognize
graphs that admit a skew partition\\
or prove that the recognition problem is ${\cal NP}$-complete.
\ei
Prove that every monster $G$ has the following properties:
\bi
\item[(vii)] for each cutset $C$ of $G$, the subgraph of $G$ induced by
$C$ is connected,
\item[(viii)] for each cutset $C$ of $G$, the subgraph of $G$ induced by
$C$ contains a $P_4$,
\item[(ix)] for each cutset $C$ of $G$, the subgraph of $G$ induced by
$C$ contains a $P_3$,
\item[(x)] for each vertex $v$ of $G$, the subgraph of $G$ induced by the
neighborhood of $v$ is connected\\
(this problem comes from Lubiw \cite{Lu}),
\item[(xi)] for each vertex $v$ of $G$, the subgraph of $G$ induced by the
neighborhood of $v$ contains a $P_4$,
\item[(xii)] for each vertex $v$ of $G$, the subgraph of $G$ induced by the
neighborhood of $v$ contains a $P_3$.
\ei
Trivially, (vii) $\Ra$ (x), (viii) $\Ra$ (xi), (ix) $\Ra$ (xii),
(viii) $\Ra$ (ix), and (xi) $\Ra$ (xii). Seinsche \cite{Se} proved
that an arbitrary graph $G$ contains a $P_4$ whenever both $G$ and
$\overline{G}$ are connected; Gallai \cite{Ga} proved that, for each
vertex $v$ of a minimal imperfect graph $G$, the neighborhood of $v$
induces a connected subgraph of the complement of $G$; hence (x) $\Ra$
(xi) and (i) \& (vii) $\Ra$ (viii). As noted earlier, a common
weakening of (vii) and (ix) has been proved by Tucker \cite{T83}:
no monster has a stable cutset; this result suggests the following
problem.
\bi
\item[(xiii)] Design a polynomial-time algorithms to recognize
graphs that have a stable cutset\\
or prove that the recognition problem is ${\cal NP}$-complete.
\ei
G.~Ravindra asked:
\bi
\item[(xiv)] What are the graphs $F$ such that no minimal imperfect
graph has a cutset that induces $F$?
\ei
\bs
Chv\'atal, Graham, Perold, and Whitesides \cite{CGPW} constructed a
class of partitionable graphs as follows. Take any factorization
$n-1=m_1m_2\cdots m_{2k}$ into integer factors $m_j$ all greater than
one; define sets $M_1,M_2,\ldots ,M_{2k}$ by $M_i=\left\{
tm_1m_2\cdots m_{i-1}: t=0,1,\ldots ,m_i-1 \right\}$ and write $
A=\sum_{i=1}^{k} M_{2i-1}$, $ B=\sum_{i=1}^{k}M_{2i}$. The
partitionable graph, with vertices $v_0, v_1,\ldots, v_{n-1}$, has
$\alpha =m_1m_3\cdots m_{2k-1}$ and $\omega =m_2m_4\cdots m_{2k}$;
with subscript arithmetic modulo $n$, its stable sets of size $\alpha$
are the $n$ sets $\{v_{j+a}:a\in A\}$ with $j=1,2,
\ldots ,n$ and its cliques of size $\omega$ are the $n$ sets
$\{v_{j-b}:b\in B\}$ with $j=1,2, \ldots ,n$. This may not specify the
graph completely: for instance, if $n=10$ and $m_1=m_2=3$ then
$A=\{0,1,2\}$, $B=\{0,3,6\}$, and so each $v_i$ may or may not be
adjacent to $v_{i+5}$; following Fr\'ed\'eric Maffray and Myriam
Preissmann, we shall say that a pair of vertices is {\em indifferent}
if it is contained in no clique of size $\omega$ and in no stable set
of size $\alpha$. In particular, the
Chv\'atal--Graham--Perold--Whitesides construction yields a large
class of partitionable graphs with rotational symmetries;
\bi
\item[(xv)] are there any other partitionable graphs with rotational
symmetries?
\ei
When either of $\alpha=$ and $\omega$ is 3 or 4, Maffray and
Preissmann \cite{MP} answered (xv) in the negative; recently,
Endre Boros and Vladimir Gurvich extended this result to the case
where either of $\alpha=$ and $\omega$ is 5.\\
Gurvich and Temkin \cite{GT} say that a clique $C$ (resp. a stable set
$S$) {\em covers} its vertex $v$ if no clique of size $\omega$ (resp.
no stable set of size $\alpha$) meets $C$ (resp. $S$) in the single
vertex $v$; we shall say that a partitionable graph has {\em property
GT\/} if at least one of its vertices is covered by a clique of size
$\omega$ as well as by a stable set of size $\alpha$. Gurvich and
Temkin observe that every partitionable graph with this property
contains a small transversal (if a vertex $u$ is covered by a clique
$C$ and a stable set $S$ then $(C-\{u\})\cup (S-\{u\})\cup (S_C \cap
C_S)$, with $S_C$ the unique stable set of size $\alpha$ disjoint from
$C$ and with $C_S$ the unique clique of size $\omega$ disjoint from
$S$, is a small transversal), and so it cannot be minimal imperfect.
Maffray and Preissmann comment: ``Actualy, G\'abor Bacs\'o has
introduced the same idea and proved the same result. He further
conjectured, using the terminology of Gurvich and Temkin, that in a
minimal imperfect graph either every vertex is not covered by a clique
or every vertex is not covered by a stable set.''
In addition, Gurvich and Temkin \cite{GT} proved that a graph arising
by the CGPW construction (which they rediscovered independently) lacks
property GT if and only if $m_1=m_3=
\cdots=m_{2k-1}=2$ or $m_2=m_4=\cdots= m_{2k}=2$, in which case the
graph, {\em regardless of the adjacencies between indifferent pairs},
contains an odd hole or an odd antihole. (An immediate corollary of
their results asserts that the CPGW construction yields no monsters; a
weaker version of this corollary was proved earlier by Grinstead
\cite{Gr}, who assumes that {\em all indifferent pairs are
nonadjacent}.) Maffray and Preissmann comment: ``We tend to believe
that there always exists a small transversal in a graph defined by the
CGPW construction, except when {\sc all} $m_i$'s are equal to two.
(In this last case it was also proved by Bacs\'o and Maffray
separately that there always exists an induced $C_5$, regardless of
indifferent pairs.)''
Finally, Gurvich and Temkin
\bi
\item[(xvi)] {\sc Conjecture:} All partitionable graphs without property GT\\
\mbox{\hspace{0.95in}}arise by the CGPW construction\\
\mbox{\hspace{0.95in}}with $m_1=m_3= \cdots=m_{2k-1}=2$ or $m_2=m_4=\cdots=m_{2k}=2$.
\ei
By virtue of their results, (xvi) implies the Strong Perfect Graph
Conjecture.
\bs
Lam, Swiercz, Thiel, and Regener \cite{LSTR} have shown that every
monster has at least 21 vertices; recently, Gurvich and Udalov
\cite{GU} raised the 21 to 25 (by verifying (xvi) for
$\alpha =3$, $\omega \leq 6$ and for $\alpha =4$, $\omega \leq 5$);
\bi
\item[(xvii)]improve this bound further.
\ei
\bs
Two cliques of size $\omega$ with $\omega -1$ vertices in common will
be called a {\em forcing\/}. If $C$ is a clique of size $\omega$ in a
minimal imperfect graph $G$, if $S$ is a stable set of size $\alpha$
in $G$, and if $C \cap S=\emptyset$, then the vertex-set of $G-(C\cup
S)$ partitions into $\alpha -1$ cliques of size $\omega -1$; each
clique of size $\omega -1$ occuring in such a partition will be called
an {\em interval\/}. The following conjectures have been contributed
by Andr\'as Seb\H o.
\bi
\item[(xviii)] {\sc Conjecture}: Every minimal imperfect graph contains a
forcing.
\item[(xix)]{\sc Conjecture:} If both a partitionable graph $G$ and its
complement contain a forcing\\
\mbox{\hspace{0.9in}} then $G$ has a small transversal.
\item[(xx)] {\sc Conjecture:} Every minimal imperfect graph with $n$
vertices contains exactly $n$ intervals.
\item[(xxi)] {\sc Conjecture:} If $G$ is minimal imperfect and if $C$ is a clique
in $G$ of size $\omega$\\
\mbox{\hspace{0.9in}} then $G-C$ is uniquely colorable.
\ei
Conjecture (xviii) is an essential weakening of a conjecture of Tucker
\cite{T84}; it comes from Fonlupt and Seb\H o \cite{FS}. Conjecture
(xix) would sharpen the main result of Markosian, Gasparian, and
Markosian \cite{MGM}, and also that of Seb\H o \cite{S92}.
In \cite{S92}, the following results are proved.
\bi
\item
A weakening of (xix), with at least two forcings in one of $G$ and
$\overline{G}$\\
(and at least one forcing in the other), holds true.
\item
Every minimal imperfect graph with
$n$ vertices contains {\em at least\/} $n$ intervals.
\item
(xx) and (xxi) are equivalent to the Strong Perfect Graph
Conjecture.
\item
No monster $G$ contains a clique $C$ of size $\omega$ and a stable
set $S$ of size $\alpha$ such that\\
$C\cap S=\emptyset$, $G-C$ is
uniquely colorable, and $\overline{G}-S$ is uniquely colorable.
\ei
\noi As a first step towards (xviii), Seb\H o proposes a weaker
\bi
\item[(xxii)] {\sc Conjecture}: Every minimal imperfect graph
with $\alpha \geq 3$ contains two families, ${\cal F}_1$ and ${\cal
F}_2$, of cliques of size $\omega$ such that, with $W_i$ standing for
the union of all the cliques in ${\cal F}_i$,\\
\mbox{\hspace{0.3in}} each ${\cal F}_i$ consists of {\em pairwise disjoint} cliques,\\
\mbox{\hspace{0.3in}} the symmetric difference of $W_1$ and $W_2$
consists of two vertices, and\\
\mbox{\hspace{0.3in}}$|{\cal F}_1|=|{\cal F}_2| \leq \alpha -2$.
\ei
Note that the two vertices in the symmetric difference of $W_1$ and
$W_2$ are necessarily nonadjacent (since they must receive the same
color in an $\omega -$coloring of the subgraph induced by $W_1 \cup
W_2$), and so (xxii) with the bound $\leq \alpha -2$ strengthened to
$=1$ reduces to (xviii). Seb\H o remarks that (xxii) with the bound $\leq
\alpha -2$ weakened to $\leq \alpha -1$ holds true: for any two
vertices, $v_1$ and $v_2$, in a stable set $S$ of size $\alpha$,
the family of $\alpha$ cliques of size $\omega$ that partitions
$G-v_i$ must include the unique clique of sixe $\omega$ disjoint from
$S$.\\
Padberg \cite{P} proved that, for each vertex $v$ of a minimal
imperfect graph $G$, the covering of $G-v$ by $\omega$ stable sets
of size $\alpha$ is unique, and so is the covering of $G-v$ by
$\alpha$ cliques of size $\omega$; Bland, Huang, and Trotter
\cite{BHT} extended this result to partitionable graphs. Both proofs
use notions of linear algebra such as linear independence and
nonsingularity of matrices.
\bi
\item[(xxiii)] [Jean Fonlupt] Give a {\em combinatorial} proof.
\ei
\newpage
\bc
{\large\bf 5. PARITY PROBLEMS}\\
\ec
\bc
***
\ec
A graph is a {\em Strict Quasi-Parity} (SQP) graph if each of its
induced subgraphs either contains an even pair or is a clique. A
graph is a {\em Quasi-Parity} (QP) graph if for each of its induced
subgraphs $H$ either $H$ is a clique or $H$ contains an even pair or
$\overline{H}$ contains an even pair. A graph is called {\em Meyniel}
if each of its cycles whose length is odd and at least five has at
least two chords (Meyniel \cite{M76} and, independently, Markosian and
Karapetian \cite{MK}, proved that these graphs are perfect.) A graph
is {\em strongly perfect} if each of its induced subgraphs contains a
stable set intersecting all maximal cliques. (These graphs, which are
perfect by definition, were introduced by Berge and Duchet
\cite{BD1}.) A graph is in $BIP^*$ if for each of its induced
subgraphs $H$ either $H$ is bipartite or one of {$H ,\overline{H}$}
contains a star cutset. (This class was introduced by Chv\'atal
\cite{C85} as {\em an example} of the more general notion of
``star-closure''; graphs in $BIP^*$ are perfect by his Star Cutset
Lemma.) A graph is {\em alternately orientable} if it admits an
orientation in which no hole contains arcs $a\ra b$ and $b\ra c$.
(These graphs were introduced by Ho\'ang \cite{Ho87}, who proved that
they are perfect.) A graph is {\em weakly triangulated} if it contains
no holes with at least five vertices and no antiholes with at least
five vertices. (These graphs were introduced by Hayward \cite{Ha85},
who proved that they are perfect.) For background material, see
\cite{Be}, \cite{He}, \cite{Hs}, \cite{R90}.
\bc
***
\ec
Here is a problem in the ``building blocks and structural faults''
spirit of Section 1:
\bi
\item[(i)] show that, for some simple class $\cal C$ of perfect
graphs, every Berge graph not in $\cal C$ contains\\
an even pair.
\ei
Again, solution of (i) would prove the Strong Perfect Graph
Conjecture. Meyniel's old problem,
\bi
\item[(ii)] characterize all minimal non-SQP graphs,
\ei
suggests a step towards (i). Stefan Hougardy proposed the following
conjectures related to (ii).
\bi
\item[(iii)] {\sc Conjecture:} Every minimal non-SQP graph is\\
the line graph of a bipartite graph or an odd hole or an antihole with
at least six vertices.
\item[(iv)] {\sc Conjecture:} Minimal imperfect graphs are minimal non-SQP
graphs.
\ei
As shown by Hougardy, (iv) is equivalent to the Strong Perfect Graph
Conjecture. To see the equivalence, note that antiholes with at least
five vertices and odd holes are minimal non-SQP graphs. This
observation and the theorem of Hayward, Ho\'ang and Maffray \cite{HCM}
asserting that every weakly triangulated graph contains an even pair
or is a clique imply that
\bc
both $G$ and $\overline G$ are minimal non-SQP graphs if and only if
$G$ is an odd hole or an odd antihole.
\ec
In turn, this fact and Lov\'asz's Perfect Graph Theorem \cite{L} show
that (iv) implies the Strong Perfect Graph Conjecture; the reverse
implication is trivial.
\bsnoi As a first step towards (iv), Hougardy proposes:
\bi
\item[(v)] prove that, for every minimal imperfect graph $G$
and every vertex $v$ of $G$,\\
$G-v$ contains an even pair.
\ei
(The property ``every vertex-deleted subgraph contains an even pair''
is weaker than the property ``every proper induced subgraph contains
an even pair or is a clique''. For example, consider $K_3 \times P_3$,
the graph consisting of triangles $v_{i1}v_{i2}v_{i3}$ with $i=1,2,3$
and paths $v_{1j}v_{2j}v_{3j}$ with $j=1,2,3$.)\\
The following problems have been proposed in the first draft and
solved in the interim.
\bi
\item[(vi)] {\tt RESOLVED}
Show that every Meyniel graph contains\\
an even pair whose identification yields a new Meyniel graph.
{\tt Frederic Maire and Irena Rusu pointed out that if we substitute
$K_2$ for each vertex of a $C_6$ then the resulting graph is a
counterexample. This counterexample had been found earlier by Marc
Bertschi and appears in his thesis. Alain Hertz communicated the fact
that Richard Sarkassian found a ten-vertex subgraph of this graph
which is also a\\ counterexample independently three years ago.}
\item[(vii)] {\tt RESOLVED}
Show that every SQP graph which is not a clique contains\\
an even pair whose identification yields a new SQP graph.
{\tt Stefan Hougardy has proved that if $G$ is a minimal non-SQP graph
graph and $e$ is any edge of $G$ which is not in a triangle, then
subdividing $e$ twice leads to a counterexample.\\ Choosing $G$ to be
$\overline{C_6}$ is one possibility. There are infinitely many
others.}
\item[(viii)]{\tt RESOLVED}
Show that for every QP graph $G$ which is not a clique,
one of $G$ and $\overline{G}$ contains\\
even pair whose identification yields a new QP graph.
{\tt Stefan Hougardy provided the following counterexample: vertices
$a,\ldots ,k$ and edges\\
$bc,cd,de,ef,fa,gh,hi,ig,ga,gf,he,hd,ic,ib,aj,jk,kb$. (This graph is
obtained from a graph\\ on vertices $a, \ldots ,i$ by subdiving the
edge $ab$ twice.)}
\ei
Hougardy's counterexamples suggest that we might want to modify (vii)
as follows:
\bi
\item[(ix)]
Show that every SQP graph which is not a clique contains\\
an even pair whose identification yields a new SQP graph\\
or an edge that belongs to no triangle.
\ei
(A similar modification might apply to (viii) and to the conjecture
of Section 1.)\\
An {\em odd pair} is a pair of non-adjacent vertices such that every
chordless path between them has an odd number of edges. Since the
first draft of this problem list was sent out, it has come to our
attention that the following question is actually still open.
\bi
\item[(x)] Show that no minimal imperfect graph contains an odd pair.
\ei
Bienstock \cite{Bi} has proved that it is co${\cal NP}$-complete to
determine if a graph contains an even pair. The next six algorithmic
questions are obvious; the three problems following them have been
around for five years:
\bi
\item[(xi)] Design a polynomial time algorithm to determine
if a perfect graph contains an even pair\\
(equivalently odd pair).
\item[(xii)] Design a polynomial time algorithm to determine
if a graph with no odd holes contains an even pair\\
(equivalently odd pair).
\item[(xiii)] Design a polynomial time algorithm to recognize
strict quasi-parity graphs.
\item[(xiv)] Design a polynomial time algorithm to recognize
quasi-parity graphs.
\item[(xv)] Design a polynomial time algorithm to determine if
a graph has an even hole.
\item[(xvi)] Design a polynomial time algorithm to determine
if a graph has an odd hole.
\item[(xvii)] Prove that strongly perfect graphs are SQP graphs.
\item[(xviii)] Prove that graphs in $BIP^*$ are SQP graphs.
\item[(xix)] Prove that alternately orientable graphs are SQP graphs.
\ei
\bs
\bc
{\large\bf 6. CONTRACTIONS}\\
\ec
\bc
***
\ec
A {\em contraction} of a graph $G$ is any graph arising from $G$ by
contracting pairwise disjoint stable sets; a {\em cograph} is a graph
containing no induced $P_4$. The following problems were contributed
by Zsolt Tuza (see also \cite{HT}). If the two stable sets in (iii) are
replaced by one then the problem is solvable in polynomial time;
J.~Kratochv\'{i}l proved that it becomes ${\cal NP}$-complete if the
two stable sets are replaced by three.
\bc
***
\ec
\bi
\item[(i)] Characterize the class of all contractions of cographs.
\item[(ii)] Characterize the class of all graphs with no imperfect
contractions.\\
(This class includes all cographs.)
\item[(iii)] How difficult is the following recognition problem?\\
INSTANCE: A perfect graph $G$ and disjoint stable sets $X,Y$ in $G$.\\
QUESTION: Is there a minimal coloring of $G$ with all vertices in $X$
red and all vertices in $Y$ blue?
\ei
\bs
\bc
{\large\bf 7. THE $P_4$-STRUCTURE}\\
\ec
\bc
***
\ec
The $P_4$-structure of a graph $G$ with vertex-set $V$ is the
hypergraph with vertex-set $V$, whose edges are the subsets of $V$
that induce $P_4$'s in $G$. A {\em disk} is the $P_4$-structure of
a hole of length at least five.
\bc
***
\ec
On the one hand, we know that perfection of a graph depends only on
its $P_4$-structure (this is a theorem of Reed \cite{R87}); on the
other hand, we don't even know how to define perfection solely in
terms of $P_4$-structure (without relying on Reed's theorem). The
``partner decomposition theorem'' mentioned in Section 3 is an
isolated example of a theorem on perfect graphs stated solely in terms
of $P_4$-structure; the following four {\em sample} problems aim to
suggest possible additional theorems of this kind.
\bi
\item[(i)] Design a polynomial-time algorithm to recognize a class
$\cal C$ of hypergraphs such that\\
the $P_4$-structure of every line-graph of a bipartite graph belongs
to $\cal C$ and such that\\
every graph with $P_4$-structure in $\cal C$
is perfect.
\item[(ii)] Design a polynomial-time algorithm to recognize a class
$\cal C$ of hypergraphs such that\\
the $P_4$-structure of every graph that has a clique-cutset belongs to
$\cal C$ and such that\\
no graph with $P_4$-structure in $\cal C$ is minimal imperfect.
\item[(iii)] Design a polynomial-time algorithm to recognize a class
$\cal C$ of hypergraphs such that\\
the $P_4$-structure of every graph that has a star-cutset belongs to
$\cal C$ and such that\\
no graph with $P_4$-structure in $\cal C$ is minimal imperfect.
\item[(iv)] Delineate a class $\cal C$ of hypergraphs such that
$\cal C$ belongs to co${\cal NP}$, such that\\
the $P_4$-structure of every graph that has an even pair belongs to
$\cal C$ and such that\\
no graph with $P_4$-structure in $\cal C$ is minimal imperfect.
\ei
All four of these problems would have trivial solutions if the
following problem were solved:
\bi
\item[(v)] Design a polynomial-time algorithm to recognize
$P_4$-structures of graphs.
\ei
Hayward \cite{Ha} designed a polynomial-time algorithm to recognize
$P_3$-structures of graphs; Ding \cite{D} designed a polynomial-time
algorithm to recognize $P_4$-structures of trees.
\bs
Two problems of a different flavor concern the $P_4$-structures
of minimal imperfect graphs: prove that each of these $P_4$-structures
has the following two properties.
\bi
\item[(vi)] Every edge extends into a disk.
\item[(vii)] For every partition of the vertex-set of the $P_4$-structure
into two disjoint nonempty parts,\\
some disk in the $P_4$-structure meets both parts.
\ei
\bs
\bc
{\large\bf 8. INTERSECTION GRAPHS}\\
\ec
\bc
***
\ec
The following problems were contributed by Zsolt Tuza (see also
\cite{T93}).
\bc
***
\ec
\bi
\item[(i)] Let $G$ be an undirected graph; let $H$ be the graph
whose vertices are the triangles in $G$,\\
two vertices of $H$ being adjacent if and only if the corresponding
triangles in $G$ share an edge.\\
For which graphs $G$ is $H$ perfect?
\item[(ii)] Let $G$ be a directed graph; let $H$ be the graph
whose vertices are the transitive triangles in $G$,\\
two vertices of $H$ being adjacent if and only if the corresponding
triangles in $G$ share an arc.\\
For which graphs $G$ is $H$ perfect?
\item[(iii)] Let $G$ be a directed graph; let $H$ be the graph
whose vertices are the cyclic triangles in $G$,\\
two vertices of $H$ being adjacent if and only if the corresponding
triangles in $G$ share an arc.\\
For which graphs $G$ is $H$ perfect?
\item[(iv)] Characterize graphs $H$ that arise as in (i).
\item[(v)] Characterize graphs $H$ that arise as in (ii).
\item[(vi)] Characterize graphs $H$ that arise as in (iii).\\
(If $G$ is a planar oriented graph then $H$ is known to be
($K_4-e$)-free Berge graph, and hence perfect.)
\ei
Comment by Leizhen Cai: for each pair of graphs $X$ and $Y$, Cai,
Corneil and Proskurowski \cite{CCP} defined the {\em
$(X,Y)$-intersection graph} of a graph $G$ as the graph whose vertices
correspond to distinct induced subgraphs of $G$ that are isomorphic
to $Y$, and where two vertices are adjacent iff the intersection of
the corresponding subgraphs contains an induced subgraph isomorphic to
$X$. In this terminology, $H$ in (i) is the $(K_2,K_3)$-intersection
graphs of $G$. Cai, Corneil and Proskurowski have shown that the
family of $(X,Y)$-intersection graphs is a subfamily of line-graphs of
$k$-uniform hypergraphs, where $k$ is the number of distinct induced
copies of $X$ in $Y$.
\newpage
\bc
{\large\bf 9. VARIATIONS ON PERFECT GRAPHS}\\
\ec
\bc
***
\ec
Karapetian, Markosian, and Reed have defined
$\beta (G)= \mbox{ max }(1+ \delta (H))$ with $\delta$ standing for
the smallest degree and with the maximum taken over all the induced
subgraphs $H$ of $G$; they call a graph $\beta$-perfect if,
for each of its induced subgraphs $F$, the chromatic number of $F$
equals $\beta (F)$.
When $q$ is a positive integer, $\alpha_q(G)$ denotes the largest
number of vertices of $G$ that can by colored with only $q$ colors;
the {\em q-norm} of a family of sets $C_1,C_2, \ldots ,C_k$ is the sum
of the $k$ numbers $min\{ |C_j|,q\}$, and $\theta_q(G)$ is the
smallest $q$-norm of a family $C_1,C_2, \ldots ,C_k$ of cliques in $G$
whose union covers all the vertices; a graph is called $q$-$perfect$
if, and only if, $\alpha_q(F)=\theta_q(F)$ for all its induced
subgraphs $F$. This concept was introduced by Lov\'asz \cite{L2}.
\bc
***
\ec
\bi
\item[(i)] Design
a polynomial-time algorithm to recognize $\beta$-perfect graphs.
\item[(ii)] Characterize $\beta$-perfect graphs in terms of forbidden
induced subgraphs.
\item[(iii)] (R. Sritharan) Conjecture: a graph contains no hole
with at least five vertices if {\em and only if}\\
each of its induced subgraphs $F$ contains an edge that is not in the
middle of any $P_4$ in $F$.\\
(Sritharan has shown that in every counterexample, each vertex must be
the middle vertex of a $P_5$.)
\item[(iv)] (Claude Berge) Is it true that every minimal
not-$3$-colorable $3$-perfect graph is perfect?
\item[(v)] (Claude Berge) Characterize $2$-perfect graphs.\\
(It is known that $2$-perfect graphs are perfect and that the converse
is false; it is known that parity graphs, balanced graphs,
comparability graphs and cocomparability graphs are perfect; see
\cite{B1,B2}.)
\ei
\bs
\bs
\bc
{\large\bf 10. BINDING FUNCTIONS AND SUCH}\\
\ec
\bc
***
\ec
As usual, $n$ is the number of vertices, $\alpha$ is the largest
size of a stable set and $\omega$ is the largest size of a clique.
The first four conjectures come from Gy\'arf\'as \cite{Gy}; trivially,
(iii)$\Ra$(ii)$\Ra$(i) and (iii)$\Ra$(iv).
\bc
***
\ec
\bi
\item[(i)] the ``Weakened Strong Perfect Graph Conjecture'':\\
There is a function $f$ such that every Berge graph\\
has chromatic number at most $f(\omega )$.
\item[(ii)]
There is a function $f$ such that every graph with no odd hole\\
has chromatic number at most $f(\omega )$.\\
(Guoli Ding asked whether $f(3)=4$.)
\item[(iii)]
For every integer $k$ there is a function $f_k$ such that
every graph with no odd hole longer than $k$\\
has chromatic number at most $f_k(\omega )$.
\item[(iv)]
For every integer $k$ there is a function $f_k$ such that
every graph with no hole longer than $k$\\
has chromatic number at most $f_k(\omega )$.
\item[(v)] (Lov\'asz; see \cite{EH}, p.39) Prove that there is
a positive $\eps$ such that\\
every Berge graph has max$\{ \alpha,\omega \} \geq n^{\eps}$.\\
(Trivially, the Strong Perfect Graph Conjecture implies $\eps =1/2$.)
\ei
\bs
\bc
{\large\bf 11. CLIQUE-TRANSVERSALS}\\
\ec
\bc
***
\ec
A {\em clique} in a graph is a maximal complete subgraph (here, as
usual, ``maximal'' is meant with respect to set-inclusion rather than
size); a {\em clique-transversal} is a set of vertices that meets all
cliques except for isolated vertices; the {\em clique-transversal
number} of a graph is the smallest size of its clique-transversal. In
strongly perfect graphs, the clique-transversal number is at most
$n/2$; in chordal graphs, if every clique has at least three vertices
then the clique-transversal number is at most $n/3$; there exist split
graphs in which every clique has at least five vertices but the
clique-transversal number exceeds $n/5$; for more on
clique-transversals, see \cite{AST} and \cite{T90}. The following
problems were contributed by Zsolt Tuza.
\bc
***
\ec
\bi
\item[(i)] Suppose that $G$ is chordal with $n$ vertices and that
every clique of $G$ has at least four vertices. Is the
clique-transversal number of $G$ at most $n/4$ ?
\item[(ii)] Suppose that $G$ is chordal with $n$ vertices and that
each edge of $G$ is contained in a clique with at least four
vertices. Is the clique-transversal number of $G$ at most $n/4$ ?
\item[(iii)] What can be said about other classes of perfect graphs if
we assume that every clique has at least $k$ vertices?
\ei
\bs
\bc
{\large\bf 12. DECOMPOSITIONS INTO PERFECT SUBGRAPHS}\\
\ec
\bc
***
\ec
The following problems, contributed by Zsolt Tuza, come from \cite{T91}.
In all of them, $G$ denotes a graph with $n$ vertices.
\bc
***
\ec
\bi
\item[(i)] {\tt RESOLVED} Can the vertex set of $G$ be partitioned
into $O(n/ \log ^2 n)$ parts such that\\ each part induces a perfect
subgraph of $G$?
{\tt Bruce Reed points out that the answer is negative since a typical
$G$ contains no induced $C_5$-free subgraph with more than $O(\log n)$
vertices, and so $\Omega(n/\log n)$ parts are needed. (As observed by
Tuza in \cite{T91}, $O(n/\log n)$ parts suffice.) One way of showing
this goes as follows. First, note that the complete graph on $t$
vertices contains $\Omega (t^2)$ edge-disjoint copies of $K_5$: the
graph whose vertices are all the $\Theta (t^5)$ copies of $K_5$
contained in the complete graph, with two vertices adjacent if and
only if the two $K_5$s share at least one edge, is regular of degree
$\Theta (t^3)$. It follows that a fixed set of $t$ vertices in a
random graph induces a $C_5$-free subgraph with probability at most
$\exp (-ct^2)$ for some positive constant $c$. Hence the probability
that the random graph contains an induced $C_5$-free subgraph with $t$
vertices is bounded from above by $n^t\exp (-ct^2)$, which tends to
zero when $t=(2/c)\ln n$.}
\item[(ii)] {\tt RESOLVED} Can the edge set of $G$ be covered with
$O(n^2 / \log^4 n)$ perfect induced subgraphs of $G$?
{\tt Again, in a typical $G$ each $C_5$-free induced subgraph has
$O(\log ^2n)$ edges, and so $\Omega(n^2 / \log^2 n)$ subgraphs are
needed; again, Tuza observed in \cite{T91} that $O(n^2 / \log^2 n)$
subgraphs suffice.}
\item[(iii)] Can the edge set of $G$ be covered with
$O(\log n / \log \log n)$ perfect subgraphs of $G$?
\ei
\bs
\begin{thebibliography}{99}
\bibitem{AST} T.~Andreae, M.~Schughart and Zs.~Tuza, {\em
Clique-transversal sets of line graphs and complements of line
graphs}, Discrete Math. {\bf 88} (1991), 11--20.
\bibitem{B1}
C.~Berge, {\em The q-perfect graphs. I.}, in: Sets, Graphs, and
Numbers (L.~Lov\'asz et al., eds.), 1992, pp.67--75.
\bibitem{B2}
C.~Berge, {\em The q-perfect graphs. II.}, RUTCOR Research Report
23-92, Rutgers University, July 1992.
\bibitem{BD1}
C.~Berge and P.~Duchet, {\em Strongly perfect graphs}, in: Topics on
Perfect Graphs. Math. Stud. 88 (C. Berge and V. Chv\'atal, eds.),
1984, pp. 57--62, MR 86g:05077.
\bibitem{BD2}
C.~Berge and P.~Duchet, {\em Perfect graphs and kernels}, Bull.Inst.
Math. Acad. Sin. {\bf 16} (1988), 263--274.
\bibitem{BD3}
C.~Berge and P.~Duchet, {\em Recent problems and results about kernels
in directed graphs}, Discrete Math. {\bf 86} (1990), 27--31.
\bibitem{Be}
M.~Bertschi, {\em Perfectly contractile graphs}, J. Combin. Theory
Ser. B {\bf 50} (1990), 222--230, MR 91j:05042.
\bibitem{BHT}
R.~G. Bland, H.-C. Huang, and L.~E.~Trotter, Jr.,{\em Graphical
properties related to minimal imperfection}, Discrete Math. {\bf 27} (1979),
11--22, MR 80g:05034.
\bibitem{Bi}
D.~Bienstock, {\em On the complexity of testing for odd holes and odd
induced paths}, Discrete Math. {\bf 90} (1991), 85--92, MR 92m:68040a.
Corrigendum in Discrete Math. {\bf 102} (1992), 109.
\bibitem{Bli}
M.~Blidia, {\em A parity graph has a kernel}, Combinatorica {\bf 6}
(1986), 23--27.
\bibitem{BDM}
M.~Blidia, P.~Duchet, and F.~Maffray, {\em On the orientation of
Meyniel graphs}, Rutcor Research Report 3-90, Rutgers University,
January 1990.
\bibitem{BE}
M.~Blidia and K.~Engel, {\em Perfectly orderable graphs and almost all
perfect graphs are kernel M-solvable}, Graphs Combin. {\bf 8} (1992),
103--108.
\bibitem{CC}
L.~Cai and D.~G.~Corneil, ``A generalization of perfect graphs ---
$i$-perfect graphs'', submitted to {\em J. Graph Theory}.
\bibitem{CCP}
L.~Cai, D.~G.~Corneil, and A.~Proskurowski, ``A generalization of
line graphs: $(X,Y)$-intersection graphs'', manuscript, 1993.
\bibitem{CFT}
G.~J.~Chang, M.~Farber, and Zs.~Tuza, {\em Algorithmic aspects of
neighborhood numbers}, SIAM J. Discr. Math. {\bf 6} (1993), 24--29.
\bibitem{C84}
V.~Chv\'atal, {\em Notes on perfect graphs}, in: Progress in
Combinatorial Optimization (W.R.Pulleublank, ed.), Academic Press,
1984, pp. 107-115.
\bibitem{C85}
V.~Chv\'atal, {\em Star-cutsets and perfect graphs}, J.Combin. Theory
Ser. B {\bf 39} (1985), 189--199, MR 87a:05060.
\bibitem{C87}
V.~Chv\'atal, {\em On the ${P}_4$ structure of perfect graphs {I}{I}{I}.
{P}artner decompositions}, J. Combin. Theory Ser. B {\bf 43} (1987),
349--353, MR 89a:05062.
\bibitem{CGPW}
V.~Chv\'atal, R.~L. Graham, A.~F. Perold, and S.~H. Whitesides, {\em
Combinatorial designs related to the strong perfect graph conjecture},
Discrete Math. {\bf 26} (1979), 83--92, MR 81b:0544.
\bibitem{CH}
V.~Chv\'atal and C.~T. Ho\`{a}ng, {\em On the ${P}_4$ structure of perfect graphs {I}.
{E}ven decompositions}, J. Combin. Theory Ser. B {\bf 39} (1985),
209--219, MR 87c:05056a.
\bibitem{CLS}
V.~Chv\'atal, W.~J.~Lenhart, and N.~Sbihi, {\em Two-colorings that decompose
perfect graphs}, J. Combin. Theory Ser. B {\bf 49} (1990), 1--9, MR 91f:05051.
\bibitem{D}
G.~Ding, {\em Recognizing the $P_4$-structure of a tree}, manuscript,
January 1993.
\bibitem{EH}
P. Erd\"os and A. Hajnal, {\em Ramsey-type theorems}, Discrete
Appl.Math. {\bf 25} (1989), 37-52.
\bibitem{FS}
J. Fonlupt and A. Seb\H o,
{\em On the clique rank and the coloration of perfect graphs},
Integer Programming and Combinatorial Optimisation {\bf 1} (1990),
(R.Kannan and W. R. Pulleyblank, eds.) Mathematical Programming
Society and University of Waterloo.
\bibitem{FU}
J.~Fonlupt and J.~P.~Uhry, {\em Transformations which preserve
perfection and H-perfection of graphs}, Bonn Workshop on Combinatorial
Optimization (Bonn 1981), pp.83--95, North-Holland Math.Stud.,66,
North-Holland, Amsterdam - New York, 1982.
\bibitem{Ga}
T.~Gallai, {\em Transitiv orientierbare {G}raphen}, Acta Math. Acad. Sci. Hungar.
{\bf 18} (1967), 25--66, MR 36 \#5026.
\bibitem{Gr}
C.~M.~Grinstead, {\em On circular critical graphs}, Discrete Math. {\bf
51} (1984), 11--24.
\bibitem{Gu92}
V.~A.~Gurvich, {\em Bilinear forms on labeled graphs} (in Russian),
Doklady Akad. Nauk {\bf 325} (1992), 221--226.
\bibitem{Gu93}
V.~A.~Gurvich, {\em Fully separated and biseparated graphs} (in
Russian), Doklady Akad. Nauk {\bf 328} (1993).
\bibitem{GT}
V.~A.~Gurvich and M.~A.~Temkin, {\em Berge's conjecture is true for
rotatable graphs} (in Russian), Doklady Akad. Nauk, to appear in Vol.
{\bf 330}.
\bibitem{GU}
V.~A.~Gurvich and V.~M.~Udalov, {\em Berge Strong Perfect Graph
Conjecture holds for any graph which has less than 25 vertices},
manuscript.
\bibitem{Gy}
A.~Gy\'arf\'as, {\em Problems from the world surrounding perfect
graphs}, Zastos. Mat. {\bf 19} (1987), 413--431.
\bibitem{Ha85}
R.~B. Hayward, {\em Weakly triangulated graphs}, J. Combin. Theory
Ser. B {\bf 39} (1985), 200--208, MR 87h:05171.
\bibitem{Ha}
R.~B.~Hayward, {\em Recognizing $P_3$-structure}, Report No. 90625-OR,
Forschungsinstitut f\"ur Diskrete Mathematik, Universit\"at Bonn,
January 1990.
\bibitem{HCM}
R.~B. Hayward, C.~Ho\`{a}ng, and F.~Maffray, {\em Optimizing weakly
triangulated graphs}, Graphs and Combinatorics {\bf 5} (1989),
339--349, MR 91c:68051a.
\bibitem{He}
A.~Hertz, {\em A fast algorithm for colouring a {M}eyniel graph}, J.
Combin. Theory Ser. B {\bf 50} (1990), 231--240, MR 91i:05111.
\bibitem{Ho87}
C.~T.~Ho\`{a}ng, {\em Alternating orientation and alternating
colouration of perfect graphs}, J. Combin. Theory Ser. B {\bf 42}
(1987), 264--273 MR 88i:05082.
\bibitem{Hoa}
C.~T.~Ho\`ang, {\em On the two-edge colourings of perfect graphs},
J. Graph Theory, to appear.
\bibitem{Hou}
S.~Hougardy, {\em Counterexamples to three conjectures concerning
perfect graphs}, Discrete Math., to appear.
\bibitem{Hs}
W.-L.Hsu, {\em Decomposition of perfect graphs}, J. Combin. Theory
Ser. B {\bf 43} (1987), 70--94.
\bibitem{HT} M.~Hujter and Zs.~Tuza, {\em Precoloring extension. III. Classes of perfect
graphs}, to appear.
\bibitem{LSTR}
C.~W.~H. Lam, S.~Swiercz, L.~Thiel, and E.~Regener, {\em A computer search for
($\alpha$, $\omega$)-graphs}, Proc. 9th Manitoba Conf. Num. Math. Comp.,
Congressus Numerantium 27, 1979, pp.~285--289, MR 82b:05002.
\bibitem{LT}
J.~Lehel and Zs.~Tuza, {\em Neighborhood perfect graphs}, Discrete
Math. {\bf 61} (1986) 93--101.
\bibitem{L}
L.~Lov\'asz, {\em Normal hypergraphs and the perfect graph
conjecture}, Discrete Math. {\bf 2} (1972), 253--267, MR 46 \#1626.
\bibitem{L1}
L.~Lov\'asz, {\em A characterization of perfect graphs}, J. Combin.
Theory Ser. B {\bf 13} (1972), 95--98, MR 46 \#8885.
\bibitem{L2}
L.~Lov\'asz, {\em Perfect graphs}, in More Selected Topics on Graph
Theory (L.M.Beineke and R.L.Wilson, eds.) (Academic Press, London-NY),
1983, pp.~55--87, MR 86h:05053.
\bibitem{Lu}
A.~Lubiw, {\em Short-chorded and perfect graphs}, J. Combin. Theory
Ser. B {\bf 51} (1991), 24--43.
\bibitem{Ma}
F.~Maffray, {\em Kernels in perfect line-graphs}, J. Combin. Th.
Ser. B {\bf 55} (1992), 1--8.
\bibitem{MGM}
S.~E.~Markosian, G.~S.~Gasparian and A.~S.~Markosian, {\em On a
conjecture of {B}erge}, J. Combin. Theory Ser. B {\bf 56} (1992),
97--107.
\bibitem{MK}
S.~E. Markosian and I.~A. Karapetian, {\em On perfect graphs} (in
Russian with an Armenian summary), Akad. Nauk Armjan. SSR Dokl. {\bf
63} (1976), 292--296, MR 56 \#8427.
\bibitem{M76}
H.~Meyniel, {\em On the perfect graph conjecture}, Discrete Math. {\bf 16 no.4}
(1976), 339--342, MR 55 \#12568.
\bibitem{M87}
H.~Meyniel, {\em A new property of critical imperfect graphs and some
consequences}, European Journal of Combinatorics {\bf 8} (1987),
313--316, MR 88k:05161.
\bibitem{MP}
F.~Maffray and M.~Preissmann, ``Near-factorizations of the cyclic
group'', manuscript, 1992.
\bibitem{O}
S.~Olariu, {\em All variations on perfectly orderable graphs}, J.
Combin. Theory Ser.B {\bf 45} (1988), 150--159.
\bibitem{P}
M.~W.~Padberg, {\em Perfect zero-one matrices}, Math. Programming {\bf
6} (1974), 180--196, MR 49 \#4809.
\bibitem{PR}
K.~R. Parthasarathy and G.~Ravindra, {\em The validity of the strong
perfect-graph conjecture for (${K}_4$ - e)-free graphs}, J. Combin.
Theory Ser. B {\bf 26} (1979), 98--100, MR 80m:05045.
\bibitem{R87}
B.~A. Reed, {\em A semi-strong perfect graph theorem}, J. Combin. Theory Ser. B {\bf 43} (1987), 223--240, MR 88g:05059.
\bibitem{R90}
B.~A. Reed, {\em Perfection, parity, planarity and packing paths}, Proceedings of
IPCO I, University of Waterloo Press, 1990.
\bibitem{S92}
A. Seb\H o, {\em Forcing colorations, and the Perfect Graph
Conjecture}, Integer Programming and Combinatorial Optimisation {\bf
2} (1992), (E. Balas, G. Cornu\'ejols and R. Kannan eds.)
Mathematical Programming Society and Carnegie Mellon University.
\bibitem{Se}
D.~Seinsche, {\em On a property of the class of n-colorable graphs}, J. Combin.
Theory Ser. B {\bf 16} (1974), 191--193, MR 49 \#2448.
\bibitem{Su}
L.~Sun, {\em Two classes of perfect graphs}, J. Combin. Theory Ser. B
{\bf 53} (1991), 273--291.
\bibitem{T83}
A.~Tucker, {\em Coloring graphs with stable cutsets}, J. Combin. Theory
Ser. B {\bf 34} (1983), 258--267.
\bibitem{T84}
A. Tucker,
{\em Uniquely colorable perfect graphs},
Discrete Math., {\bf 44} (1984), 187--194.
\bibitem{T87}
A. Tucker, Coloring perfect $K_4-e$-free graphs, J. Combin.
Theory Ser. B {\bf 42} (1987), 313-318.
\bibitem{T90} Zs.~Tuza, {\em Covering all cliques of a graph}, Discrete
Math. {\bf 86} (1990), 117--126.
\bibitem{T91} Zs.~Tuza, {\em Perfect
graph decompositions}, Graphs Combin. {\bf 7} (1991), 89--93.
\bibitem{T93} Zs.~Tuza, {\em Perfect triangle families}, Bull. London
Math. Soc., to appear.
\end{thebibliography}
\end{document}