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