Here is a Romanian translation of this web page (by Web Geek Science)

As a part of the 1992  1993 Special Year on Combinatorial Optimization at DIMACS, László Lovász, Bruce Reed, and I organized a workshop on perfect graphs. The workshop took place at Princeton University on June 1014, 1993. In February of that year, Bruce and I prepared a list of open problems, which was then sent to all the invited participants. The next version of the list, updated just before the workshop, and still available at
If you have
Vašek Chvátal
Related pages:
This collection is written for people with at least a basic knowledge of perfect graphs. Uninformed neophytes may look up the missing definitions on the web in Alexander Schrijver's lecture notes or in Jerry Spinrad's draft of a book on efficient graph representations etc. or in MathWorld. Books on perfect graphs include
1. Recognition of perfect graphs
2. Optimization in perfect graphs
3. Structure of partitionable graphs
4. The P_{4}structure and its relatives
5. Parity pairs and perfectly contractile graphs
6. Graphs without odd holes (and graphs without even holes)
7. Intersection graphs
8. qperfect graphs
In November 2002, this section became obsolete: perfect graphs can be recognized in polynomial time. See
M. Chudnovsky, G. Cornuéjols, X. Liu, P.D. Seymour, and K. Vušković, Recognizing Berge Graphs, Combinatorica 25 (2005), 143186.
Can these four optimization problems be solved for perfect graphs
by polynomialtime algorithms of purely combinatorial nature avoiding
the numerical instability of the ellipsoid method? The decomposition
theorem for perfect graphs does not  or at least does not yet 
provide such algorithms; warmup exercises consist of trying to
design such algorithms for restricted classes of perfect graphs. One
of these infinitely many warmup problems is singled out here.
<
in such a way that no
induced P_{4} with vertices a,b,c,d
and edges
ab,bc,cd
has a<b
and d<c
.
Chvátal (Perfectly ordered graphs. Topics on perfect
graphs, NorthHolland Math. Stud., 88, NorthHolland, AmsterdamNew
York, 1984, pp. 6365. MR
86j:05059) has shown that, given a perfectly ordered
graph G
and its coloring  by some number k
of colors  constructed by the familiar greedy algorithm, one can
find a clique of k
vertices in G
in
polynomial time; it follows that perfectly ordered graphs are
perfect.
Problem 2.1. Design a polynomialtime algorithm of purely combinatorial nature that, given a perfectly ordered graphG
, constructs a largest stable set inG
.

1 vertices which meets
all cliques of size omega(G) and all stable sets of size
alpha(G). The following problem is an easier variation on a
conjecture contributed to the 1993 workshop by Gurvich and Temkin and
on two conjectures proposed by Bacsó, Boros, Gurvich, Maffray,
and Preissmann (On minimal imperfect graphs with circular
symmetry, J. Graph Theory 29 (1998),
209225. MR
2000h:05116).
Conjecture 3.1. Every partitionable graph G with alpha(G)>2 and omega(G)>2One of the milestones in the development of our understanding of perfect graphs was the theorem of Lovász (A characterization of perfect graphs, J. Combinatorial Theory Ser. B 13 (1972), 9598. MR 46 #8885) asserting that every minimal imperfect graph G has precisely
has a small transversal or else contains a hole of length five.
A partitionable graph without a small transversal has been constructed
by by Chvátal, Graham, Perold, and Whitesides (op.cit.). Its
vertices are 0,1,...,16
; vertices i
and
j
are adjacent if and only if ij
mod 17 is one of
1,3,4,5,12,13,14,16
.
1  4  8  12  15  1
Helpful hints in the direction of Conjecture 3.1 are the results of
Bacsó, Boros, Gurvich, Maffray, and Preissmann (op.cit.); these
involve the construction of partitionable graphs with rotational
symmetries designed by Chvátal, Graham, Perold, and Whitesides
(op.cit.), which goes as follows.
Take any factorization
Bacsó, Boros, Gurvich, Maffray, and Preissmann (op. cit.) say that a CGPW graph is of Type 2 if it has both of the properties
A helpful result on small transversals (called the "Parent Lemma" in the paper of Bacsó, Boros, Gurvich, Maffray, and Preissmann) goes as follows. In a partitionable graph G, a clique C of size omega(G) is a mother of a vertex v if no clique of size omega(G) meets C in the single vertex v; a stable set S of size alpha(G) is a father of a vertex v if no stable set of size alpha(G) meets S in the single vertex v. Gurvich and Temkin (Berge's conjecture holds for rotational graphs.(Russian) Dokl. Akad. Nauk 332 (1993), 144148. MR 94m:05156) and, independently, Bacsó proved that
if some vertex in a partitionable graph has both parents,
then the graph has a small transversal.
The following problem, related to Conjecture 3.1, has been contributed to the 1993 workshop by András Sebö.
Problem 3.2. True or false? If a partitionable graph G contains two cliques of size omega(G) with omega(G)1 vertices in common and two stable sets of size alpha(G) with alpha(G)1 vertices in common, then G has a small transversal.An affirmative solution of Problem 3.2 would sharpen the main result of Markosyan, Gasparyan, and Markosyan (On a conjecture of Berge, J. Combin. Theory Ser. B 56 (1992), 97107. MR 93h:05078) and also that of Sebö ( Forcing colorations, and the perfect graph conjecture, Integer Programming and Combinatorial Optimization 2 (E. Balas, G. Cornuéjols, and R. Kannan, eds.), Mathematical Programming Society and Carnegie Mellon University, 1992).
Problem 3.3. Prove that, in every partitionable graph other than C_{5},From results of
every P_{4} extends into a P_{5} or the complement of a P_{5}.
in every partitionable graph,
every P_{4} extends into a P_{5} or the complement of a P_{5} or a C_{5}.
I(G)
such that
G'
is the complement of G
, then
I(G)
=I(G')
,
I(G)
=I(G')
, then G
and G'
are either both perfect or both imperfect
G
could be expressed exclusively in terms of some such natural
invariant.The finest invariant with properties (i) and (ii) assigns to each
graph G
the unordered pair consisting of G
and its complement; the coarsest invariant with properties (i) and
(ii) sets
I(G)=1
if G
is perfect and
I(G)=0
if G
is imperfect.
P_{4}
structure of G
; this
invariant is defined as the hypergraph whose vertexset V
is
vertexset of G
and whose edges are the subsets of
V
that induce P_{4}
's in
G
. For example, here are two graphs with the same
P_{4}
structure,
{a,b,c,d}, {b,c,d,e}, {c,d,e,f}, {d,e,f,a}, {e,f,a,b}, {f,a,b,c}: a b oo a b c / \ ooo / \    / \    f o o c    \ /    \ /    \ / ooo oo d e f e dSince
P_{4}
is a selfcomplementary graph, the
P_{4}
structure of G
has property
(i); Chvátal (A semistrong perfect graph conjecture.
Topics on perfect graphs, NorthHolland Math. Stud., 88,
NorthHolland, AmsterdamNew York, 1984, pp. 279280. MR
86j:05119) conjectured and Reed (A semistrong perfect
graph theorem, J. Combin. Theory Ser. B 43
(1987), 223240. MR
88g:05059) proved that it has property (ii) as well.Additional graph invariants with properties (i) and (ii), found by Chính Hoàng, are
G
, defined as the hypergraph whose vertexset
V
is vertexset of G
and whose edges are the
subsets of V
that induce C_{5}
or
the paw (the graph with vertices a,b,c,d
and edges
ab,ac,bc,cd
) or the complement of the paw in
G
(C. T. Hoàng, On the
discstructure of perfect graphs. I. The copawstructure,
Proceedings of the Third International Conference on Graphs and
Optimization, GOIII (Leukerbad, 1998), Discrete Appl. Math.
94 (1999), 247262. MR
2001a:05065);
G
, defined as the hypergraph whose vertexset
V
is vertexset of G
and whose edges are the
subsets of V
that induce C_{5}
or
C_{4}
or the complement of
C_{4}
in G
(C. T. Hoàng, On the discstructure of perfect
graphs. II. The coC_{4}structure, Discrete
Math. 252 (2002), 141159);
G
, defined as the hypergraph whose vertexset
V
is vertexset of G
and whose edges are the
subsets of V
that induce P_{3}
or
the complement of P_{3}
in G
(C. T. Hoàng, On the
coP_{3}structure of perfect graphs, to appear in
SIAM J. Discrete Math.);
G
, defined as the hypergraph whose vertexset
V
is vertexset of G
and whose edges are the
subsets of V
that induce K_{3}
or
the complement of K_{3}
in G
(since K_{3},P_{3},coP_{3}
, and
coK_{3}
are the only graphs with three vertices,
two graphs have the same
coP_{3}structure if and only if
they have the same
coK_{3}structure).
P_{4}
structure
applies  with suitable modifications  to Hoàng's invariants
as well.
Let us define an odd ring as the 4uniform hypergraph with vertices
u_{0}, u_{1}, ..., u_{k1}
k
is odd and at least five and with the
k
edges
{u_{i+1}, u_{i+2}, u_{i+3}, u_{i+4}}
k
. It is easy, if a
little tedious, to show that a graph is a Berge graph if and only if
its P_{4}
structure contains no induced odd ring;
this fact led in the past to speculations about possible certificates,
elegant, easily verifiable, and expressed exclusively in terms of
4uniform hypergraphs, that a prescribed
P_{4}
structure contains no induced odd ring. Finding such a certificate is at least as difficult as the  as
yet unsolved  problem of showing that the class of Berge graphs
belongs to NP. A less ambitious program would be an attempt to
reformulate the decomposition
theorem for perfect graphs by Chudnovsky, Robertson, Seymour, and
Thomas exclusively in terms of
P_{4}
structure.
The decomposition theorem asserts that
every Berge graph either belongs to one of five classes of basic Berge graphs, namely,(for definitions, see the paper by Chudnovsky, Robertson, Seymour, and Thomas); in her thesis, Chudnovsky showed that the stronger assertion with Mjoins dropped remains valid. Do the remaining three structural faults admit natural counterparts formulated exclusively in terms ofor else it has one of four structural faults, namely,
 bipartite graphs,
 complements of bipartite graphs,
 linegraphs of bipartite graphs,
 complements of linegraphs of bipartite graphs,
 "double split graphs",
 2join,
 2join in the complement,
 Mjoin,
 a balanced skew partition
P_{4}
structure?
The following two problems represent one attempt to state this question in precise terms.
Problem 4.1. Find a class C_{1} of 4uniform hypergraphs such that
 the
P_{4}
structure of a graph belongs to C_{1} if and only if it is theP_{4}
structure of a (possibly different) graph such that this graph or its complement admits a 2join membership in C_{1} can be tested in polynomial time.
Problem 4.2. Find a class C_{2} of 4uniform hypergraphs such thatIt is conceivable that these problems can be solved by building up on the following three results:
 the
P_{4}
structure of a graph belongs to C_{2} if and only if it is theP_{4}
structure of a (possibly different) graph that admits a balanced skew partition, membership in C_{2} can be tested in polynomial time.
P_{4}
structures of graphs,
P_{4}
structure does not fit the
intuitive meaning of the expression "exclusively in terms of
P_{4}
structure".
This class is defined in terms of a certain directed graph,
 the
P_{4}
structure of every basic Berge graph belongs to C, no 4uniform hypergraph in C contains an induced odd ring,
 membership in C can be tested in polynomial time.
D_{6}(H)
, associated with every 4uniform hypergraph
H
: C consists of all 4uniform
hypergraphs H
such that
The vertices of
H
contains no induced ring with five vertices and all strongly connected components of
D_{6}(H)
are bipartite.
D_{6}(H)
are all the ordered
6tuples
(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6})
H
such that the subhypergraph of H
induced by the set
{u_{1},u_{2},u_{3},u_{4},u_{5},u_{6}}
{u_{1},u_{2},u_{3},u_{4}},
{u_{2},u_{3},u_{4},u_{5}},
{u_{3},u_{4},u_{5},u_{6}};
(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6})
D_{6}(H)
to vertex
(v_{1},v_{2},v_{3},v_{4},v_{5},v_{6})
D_{6}(H)
if and only if
v_{1}=u_{2}, v_{2}=u_{3},
v_{3}=u_{4}, v_{4}=u_{5},
v_{5}=u_{6}.
Trivially, membership in C can be tested in
polynomial time; trivially, no 4uniform hypergraph in
C contains an induced odd ring; a proof that the
P_{4}
structure of every basic Berge graph
belongs to C is based on the following observation
(verified by exhaustive search and used also in the proof that a graph
is a Berge graph if and only if its
P_{4}
structure contains no induced odd ring):
TheNow consider an arbitrary graphP_{4}
structure of a graphF
with verticesconsists of hyperedges u_{1},u_{2},u_{3},u_{4},u_{5},u_{6}
{u_{1},u_{2},u_{3},u_{4}}, {u_{2},u_{3},u_{4},u_{5}}, {u_{3},u_{4},u_{5},u_{6}}
only if
F
is isomorphic (as an unlabeled graph) with one of the following six graphs:
F_{1}
is the pathP_{6}
;F_{2}
is the complement ofF_{1}
;F_{3}
consists of verticesa,b,c,d,e,f
and edgesab,bc,cd,eb,fb,fc,fe
;F_{4}
is the complement ofF_{3}
;F_{5}
consists of verticesa,b,c,d,e,f
and edgesab,bc,cd,de,fb,fc
;F_{6}
is the complement ofF_{5}
.
G
and let H
denote its
P_{4}
structure; we shall say that a vertex
(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6})
D_{6}(H)
is of type i
if
the subgraph of G
induced by
{u_{1},u_{2},u_{3},u_{4},u_{5},u_{6}}
F_{i}
. The next observation
(also verified by exhaustive search and also used in
the proof that a graph is a Berge graph if and only if its
P_{4}
structure contains no induced odd ring) is this:
Each vertex ofIt follows thatD_{6}(H)
with nonzero indegree and nonzero outdegree has one of the following four properties:
 it is of type
1
and all its neighbors are of type1,5,
or6
; it is of type
2
and all its neighbors are of type2,5,
or6
; it is of type
3
and all its neighbors are of type4
; it is of type
4
and all its neighbors are of type3
.
each strongly connected component ofD_{6}(H)
with at least two vertices has one of the following three properties:
 all of its vertices are of type
1
; all of its vertices are of type
2
; it is bipartite, all its vertices in one part of the bipartition are of type
3
, and all its vertices in the other part of the bipartition are of type4
.
Finally, assuming that G
is a basic Berge graph, we shall
verify that all strongly connected components of
D_{6}(H)
are bipartite. Since
P_{4}
structure of G
is invariant
under complementation of G
, we may distinguish between
three cases.
Case 1: G
is bipartite.
Since F_{2}
is not bipartite, we only need to
twocolor each strongly connected component of
D_{6}(H)
whose vertices are of type
1
. This can be done by giving each of these
vertices,
(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6}),
u_{1}
in G
.Case 2: G
is the linegraph of a bipartite graph.
The twocoloring of the vertices of the bipartite graph induces a
twocoloring of the edges of G
such that the two edges of
any induced P_{3}
in G
have distinct
colors. Since F_{2}
is not a linegraph of a
bipartite graph, we only need to twocolor each strongly connected
component of D_{6}(H)
whose vertices are of type
1
. This can be done by giving each of these vertices,
(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6}),
u_{1}u_{2}
in G
.Case 3: G
is a double split graph.
By definition, G
has 2m+2n
(m,n>1
)
distinct vertices,
a_{1},...,a_{m}, b_{1},...,b_{m},
c_{1},...,c_{n}, d_{1},...,d_{n},
a_{i}
is adjacent to a b_{j}
if and only if i=j
,
c_{i}
is nonadjacent to a d_{j}
if and only if i=j
,
{a_{i},b_{i},c_{j},d_{j}}
induces a P_{4}
.
(u_{1},u_{2},u_{3},u_{4},u_{5},u_{6})
D_{6}(H)
that is of type 1
must have
u_{1},u_{3},u_{4},u_{6}
in
{a_{1},...,a_{m},b_{1},...,b_{m}}
u_{2},u_{5}
in
{c_{1},...,c_{n},d_{1},...,d_{n}};
1
are adjacent.
Since the complement of a double split graph is a double split graph, no two vertices of
type 2
are adjacent, either.Here are a few results on recognizing P_{4}structures of graphs:
P_{4}
structures of trees,
P_{4}
structures of linegraphs of bipartite
graphs,
P_{4}
structures of bipartite graphs.
P_{4}
structures of connected graphs whose
2connected components are cliques.
P_{4}
structures of graphs.
An even pair is a pair of vertices such that every
chordless path between them has an even number of
edges. J. Fonlupt and J.P. Uhry (Transformations which
preserve perfectness and Hperfectness of graphs, Bonn Workshop
on Combinatorial Optimization (Bonn, 1980), Ann. Discrete Math., 16,
NorthHolland, AmsterdamNew York, 1982, pp. 8395. MR
84f:05076) and H. Meyniel (A new property of critical
imperfect graphs and some consequences, European
J. Combin. 8 (1987), 313316. MR
88k:05082) proved that contracting an even pair
in a graph G
(which means deleting both vertices of the
even pair, introducing a brand new vertex, and making the neighborhood
of this new vertex equal to the union of the neighborhoods of the two
deleted vertices) changes neither the clique number of G
nor the chromatic number of G
.
M.E. Bertschi (Perfectly contractile graphs,
J. Combin. Theory Ser. B 50 (1990), 222230. MR
91j:05042) defined an evencontractile graph as
any graph G
for which there is a sequence
G_{0}, G_{1}, ..., G_{k}
G_{0}=G
,
G_{t+1}
arises by
contracting an even pair in G_{t}
,
G_{k}
is a clique
G
such that all induced subgraphs of
G
are evencontractile. (The results of Meyniel
guarantee that every perfectly contractile graph is perfect.)Hazel Everett and Bruce Reed contributed to the 1993 workshop a number of conjectures on even pairs and perfectly contractile graphs; two of them are singled out here. The odd stretcher in the first of them is any graph that consists of three vertexdisjoint triangles and three vertexdisjoint paths, each path having an odd number of edges and one endpoint in each of the two triangles. (In particular, the smallest odd stretcher is the antihole with six vertices.)
Conjecture 5.1. A graph is perfectly contractile if and only if it contains no odd hole, no antihole, and no odd stretcher.
Conjecture 5.2. Every perfectly contractile graph other than a clique contains an even pair whose contraction leaves the graph perfectly contractile.
Bienstock (On the complexity of testing for odd holes and induced odd paths, Discrete Math. 90 (1991), 8592. MR 92m:68040a Corrigendum: Discrete Math. 102 (1992), 109. MR 92m:68040b) has proved that it is coNPcomplete to determine if a graph contains an even pair. By analogy with the notion of en even pair, an odd pair is a pair of nonadjacent vertices such that every chordless path between them has an odd number of edges. The following two algorithmic problems are obvious.
Problem 5.3. Design a polynomialtime algorithm to determine
if a perfect graph contains an even pair.
Problem 5.4. Design a polynomialtime algorithm to determine
if a perfect graph contains an odd pair.
Other problems on path parity and perfection, including additional conjectures contributed to the 1993 workshop by Everett and Reed, can be found in
Problems 6.16.3 come from András Gyárfás (Problems from the world surrounding perfect graphs, Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastos. Mat. 19 (1987), 413441. MR 89e:05089).
Problem 6.1. Prove the existence of a function g such thatGuoli Ding asked whether g(3)=4. His question has been answered in the affirmative by Robertson, Seymour, and Thomas, who provided a structural characterization of graphs without odd holes and without K_{4}.
every graph G with no odd hole has chromatic number at most g(omega(G)).
Problem 6.2. For all positive integers k, prove the existence of a function g_{k} such that every graph G with no odd hole longer than k has chromatic number at most g_{k}(omega(G)).
Problem 6.3. For all positive integers k, prove the existence of a function h_{k} such that every graph G with no hole longer than k has chromatic number at most h_{k}(omega(G)).
Chính Hoàng and
Colin McDiarmid (On the divisibility of graphs, Discrete
Math. 242 (2002), 145156. MR 1
874 761) say that a graph is 2divisible
if, for each of its induced subgraphs F
, the vertexset
of F
can be partitioned into subsets
S_{1}
and S_{2}
in such a
way that every largest clique in F
meets both
S_{1}
and S_{2}
. Trivially,
no odd hole is 2divisible, and so every 2divisible graph is
oddholefree; Hoàng and McDiarmid conjectured the converse:
Conjecture 6.4. Every oddholefree graph is 2divisible.Hoàng and McDiarmid proved Conjecture 6.4. for clawfree graphs and noted that it also holds for graphs without K_{4} (since g(3)=4 in Problem 6.1).
Can something similar be said about graphs without even holes? The
notion of 2divisibility generalizes: Hoàng and McDiarmid say
that a graph is kdivisible if, for each of its induced
subgraphs F
, the vertexset of F
can be
partitioned into subsets S_{1}
,
S_{2}
, ..., S_{k}
in such a
way that no S_{i}
contains a largest clique in
F
.
Conjecture 6.5. (Hoàng) Every evenholefree graph is 3divisible.
Conjecture 6.6. (Hoàng) Every evenholefree graphConjecture 6.6 implies Conjecture 6.5: more generally, ifG
is colorable bycolors. 2·omega(G)1
G
is a graph and
k
is an integer such that
k·(omega(G)1) >= chi(G),
G
is k
divisible.The following conjecture comes from Hayward and Reed (Forbidding holes and antiholes, in: Perfect Graphs (J.L. RamírezAlfonsín and B.A . Reed, eds.), Wiley, 2001, pp. 113137. MR 1 861 360):
Conjecture 6.7. Every evenholefree graph includes a vertex whose neighborhood can be partitioned into two cliques.Conjecture 6.7 implies Conjecture 6.6: more generally, if every induced subgraph of a graph
G
includes a vertex of degree
at most t
, then G
is
t+1
colorable.Conforti, Cornuéjols, Kapoor, and Vušković (Evenholefree graphs. II. Recognition algorithm. J. Graph Theory 40 (2002), 238266) designed a polynomial algorithm to recognize evenholefree graphs.
Problem 6.8. Design a polynomial algorithm to recognize oddholefree graphs.
Problems 7.17.6 were contributed by Zsolt Tuza before the 1993 workshop (see also Tuza, Perfect triangle families, Bull. London Math. Soc. 26 (1994), 321324. MR 96b:05083).
Problem 7.1. For every (undirected) graph G, let H_{1}(G) denote the graph whose vertices are the triangles in G, two vertices of H_{1}(G) being adjacent if and only if the corresponding triangles in G share an edge.In a slightly related paper, Akiyama and Chvátal (Packing paths perfectly, Discrete Math. 85 (1990), 247255. MR 92a:68114) studied graphs H'(G) whose vertices are (not necessarily induced) paths P_{3} in G, two vertices of H'(G) being adjacent if and only if the corresponding P_{3}'s in G share at least one vertex; they characterized (undirected) graphs G for which H'(G) is perfect. Another related paper is Lê, Perfect kline graphs and ktotal graphs, J. Graph Theory 17 (1993), 6573. MR 94b:05083.
For which graphs G is H_{1}(G) perfect?
Problem 7.2. For every directed graph G, let H_{2}(G) denote the graph whose vertices are the transitive triangles in G, two vertices of H_{2}(G) being adjacent if and only if the corresponding triangles in G share an arc.
For which graphs G is H_{2}(G) perfect?
Problem 7.3. For every directed graph G, let H_{3}(G) denote the graph whose vertices are the cyclic triangles in G, two vertices of H_{3}(G) being adjacent if and only if the corresponding triangles in G share an arc.
For which graphs G is H_{3}(G) perfect?
Problem 7.4. Charaterize graphs H such that
H=H_{1}(G) for some graph G.
Problem 7.5. Charaterize graphs H such that
H=H_{2}(G) for some directed graph G.
Problem 7.6. Charaterize graphs H such thatIf G is a planar oriented graph, then H_{3}(G) is known to be (K_{4}e)free Berge graph, and hence perfect.
H=H_{3}(G) for some directed graph G.
Comment by Leizhen Cai: for each pair of graphs X and Y, Cai, Corneil and Proskurowski (A generalization of line graphs: (X,Y)intersection graphs, J. Graph Theory 21 (1996), no. 3, 267287. MR 96m:05164) defined the (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_{1}(G) 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 linegraphs of kuniform hypergraphs, where k is the number of distinct induced copies of X in Y.
The following problems were contributed to the 1993 workshop by Claude Berge.
Problem 8.1 Characterize 2perfect graphs.
Problem 8.2. Is it true that every minimal not3colorable 3perfect graph is perfect?It is known that 2perfect graphs are perfect and that the converse is false; it is known that parity graphs, balanced graphs, comparability graphs and cocomparability graphs are 2perfect; see C. Berge, The qperfect graphs. I. The case q=2. Sets, graphs and numbers (Budapest, 1991; L. Lovász, D. Miklos, and T. Szönyi, eds.), Colloq. Math. Soc. János Bolyai, 60, NorthHolland, Amsterdam, 1992, pp.6775. MR 94d:05110 and C. Berge, The qperfect graphs. II.Combinatorics 92 (Catania, 1992), Matematiche (Catania) 47 (1992), 205211 (1993). MR 95h:05126 and C. Berge, The qperfect graphs. Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), WileyIntersci. Publ., Wiley, New York, 1995, pp.4762. MR 97c:05060.