PERFECT PROBLEMS

Created on 22 August, 2000
Last updated on 5 July, 2006

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


In May 2002,
the Strong Perfect Graph Conjecture
became
the Strong Perfect Graph Theorem

Details are here.
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 10--14, 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
ftp://dimacs.rutgers.edu/pub/perfect/problems.tex
included additions by Claude Berge, Leizhen Cai, Guoli Ding, Vladimir Gurvich, András Gyárfás, Alain Hertz, Stefan Hougardy, Frédéric Maire, Frédéric Maffray, K. R. Parthasarathy, Myriam Preissmann, G. Ravindra, Irena Rusu, András Sebö, R.Sritharan, and Zsolt Tuza. Most of the problems presented here come from that list.

If you have

please, send them to me.

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

Contents of this page:

1. Recognition of perfect graphs
2. Optimization in perfect graphs
3. Structure of partitionable graphs
4. The P4-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. q-perfect graphs

1. RECOGNITION OF PERFECT 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), 143--186.

To the table of contents

2. OPTIMIZATION IN PERFECT GRAPHS

Grötschel, Lovász, and Schrijver (Polynomial algorithms for perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 325--356; MR 86g:05073) showed that the weighted versions of are solvable in polynomial time for perfect graphs. Their algorithms are based on the ellipsoid method and a polynomial time separation algorithm for a certain class of positive semidefinite matrices related to Lovász' upper bound (On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), 1--7; MR 81g:05095) on the Shannon capacity of a graph.

Can these four optimization problems be solved for perfect graphs by polynomial-time 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; warm-up exercises consist of trying to design such algorithms for restricted classes of perfect graphs. One of these infinitely many warm-up problems is singled out here.

A graph is called perfectly ordered if its vertex-set is endowed with a linear order < in such a way that no induced P4 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, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 63--65. 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 polynomial-time algorithm of purely combinatorial nature that, given a perfectly ordered graph G, constructs a largest stable set in G.

To the table of contents

3. STRUCTURE OF PARTITIONABLE GRAPHS

Following Bland, Huang, and Trotter (Graphical properties related to minimal imperfection, Discrete Math. 27 (1979), 11--22. MR 80g:05034; Graphical properties related to minimal imperfection. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 181--192. MR 86e:05075), a graph is called partitionable if, for some r and s, it has rs+1 vertices and, no matter which vertex is removed, the set of the remaining rs vertices can be partitioned into r pairwise disjoint cliques of size s and also into s pairwise disjoint stable sets of size r. Odd holes and odd antiholes are partitionable; many additional partitionable graphs have been constructed by V. Chvátal, R. L. Graham, A. F. Perold, and S. H. Whitesides (Combinatorial designs related to the strong perfect graph conjecture, Discrete Math. 26 (1979), 83--92 MR 81b:05044)).

A small transversal in a graph G is a set of alpha(G)+omega(G)-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), 209--225. MR 2000h:05116).

Conjecture 3.1. Every partitionable graph G with alpha(G)>2 and omega(G)>2
has a small transversal or else contains a hole of length five.
One 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), 95--98. MR 46 #8885) asserting that every minimal imperfect graph G has precisely
alpha(G)omega(G) +1
vertices. This theorem implies that every minimal imperfect graph is partitionable and that -- as pointed out by Chvátal (Notes on perfect graphs, Progress in combinatorial optimization (Waterloo, Ont., 1982), Academic Press, Toronto, Ont., 1984, pp. 107--115. MR 86h:05091) -- no minimal imperfect graph contains a small transversal. It follows that a proof of Conjecture 3.1 would provide another proof of the Strong Perfect Graph Theorem.

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 |i-j| mod 17 is one of

1,3,4,5,12,13,14,16.
Ara Markosian claims (here) that this is the only known partitionable graph without a small transversal. One of the many holes of length five in this graph is
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

n-1=m1m2... m2k
into integer factors mj all greater than one; define sets M1,M2,... ,M2k by
Mi={ tm1m2... mi-1: t=0,1,... ,mi-1}
and write
A=M1+M3+...M2k-1,   B=M2+M4+...M2k
The partitionable graph, with vertices v0 , v1,..., vn-1, has
alpha=m1m3...m2k-1 and omega=m2m4...m2k ;
with subscript arithmetic modulo n, its stable sets of size alpha are the n sets
{vj+a:a in A} with j=1,2, ... ,n
and its cliques of size omega are the n sets
{vj-b:b in B} with j=1,2, ... ,n.
This may not specify the graph completely: for instance, if n=10 and m1=m2=3, then A={0,1,2}, B={0,3,6}, and so each vi may or may not be adjacent to vi+5. More generally, following Frédéric Maffray and Myriam Preissmann, a pair of vertices is called indifferent if it is contained in no clique of size omega and in no stable set of size alpha; indifferent pairs may or may not be adjacent in the CGPW graph.

Bacsó, Boros, Gurvich, Maffray, and Preissmann (op. cit.) say that a CGPW graph is of Type 2 if it has both of the properties

m1=m3=...=m2k-1=2
and
m2=m4=...=m2k=2;
they say that the graph is of Type 1 if it has precisely one of these properties; they say that the graph is of Type 0 if it has neither of them. They prove that

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), 144--148. 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), 97--107. 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 C5,
every P4 extends into a P5 or the complement of a P5.
From results of and it follows that
in every partitionable graph,
every P4 extends into a P5 or the complement of a P5 or a C5.

To the table of contents

4. THE P4-STRUCTURE AND ITS RELATIVES

The Perfect Graph Theorem of Lovász (Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), 253--267. MR 46 #1624) asserts that a graph is perfect if and only if its complement is perfect. Musings on the relationship of this theorem to possible certificates of perfection led Chvátal in the late 1970's and the early 1980's to look for graph invariants I(G) such that
  1. if G' is the complement of G, then I(G)=I(G'),
  2. if I(G)=I(G'), then G and G' are either both perfect or both imperfect
in the hope that an elegant and easily verifiable certificate of perfection of 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.
One natural invariant that interpolates between these two extremes is the P4-structure of G; this invariant is defined as the hypergraph whose vertex-set V is vertex-set of G and whose edges are the subsets of V that induce P4's in G. For example, here are two graphs with the same P4-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
        o--------o           a         b         c         
       /          \          o---------o---------o
      /            \         |         |         |
     /              \        |         |         |
  f o                o c     |         |         |
     \              /        |         |         |
      \            /         |         |         |
       \          /          o---------o---------o
        o--------o           d         e         f
        e        d
Since P4 is a self-complementary graph, the P4-structure of G has property (i); Chvátal (A semistrong perfect graph conjecture. Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 279--280. MR 86j:05119) conjectured and Reed (A semistrong perfect graph theorem, J. Combin. Theory Ser. B 43 (1987), 223--240. 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

Our subsequent discussion of P4-structure applies -- with suitable modifications -- to Hoàng's invariants as well.

Let us define an odd ring as the 4-uniform hypergraph with vertices

u0, u1, ..., uk-1
where k is odd and at least five and with the k edges
{ui+1, ui+2, ui+3, ui+4}
where the subscripts are taken modulo k. It is easy, if a little tedious, to show that a graph is a Berge graph if and only if its P4-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 4-uniform hypergraphs, that a prescribed P4-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 P4-structure.

The decomposition theorem asserts that

every Berge graph either belongs to one of five classes of basic Berge graphs, namely, or else it has one of four structural faults, namely,
(for definitions, see the paper by Chudnovsky, Robertson, Seymour, and Thomas); in her thesis, Chudnovsky showed that the stronger assertion with M-joins dropped remains valid. Do the remaining three structural faults admit natural counterparts formulated exclusively in terms of P4-structure?

The following two problems represent one attempt to state this question in precise terms.

Problem 4.1. Find a class C1 of 4-uniform hypergraphs such that
Problem 4.2. Find a class C2 of 4-uniform hypergraphs such that
It is conceivable that these problems can be solved by building up on the following three results: However, defining C1 or C2 through properties of graphs with a prescribed P4-structure does not fit the intuitive meaning of the expression "exclusively in terms of P4-structure".


As for the five classes of basic Berge graphs, we are about to define a class C of 4-uniform hypergraphs such that

This class is defined in terms of a certain directed graph, D6(H), associated with every 4-uniform hypergraph H: C consists of all 4-uniform hypergraphs H such that
The vertices of D6(H) are all the ordered 6-tuples
(u1,u2,u3,u4,u5,u6)
of distinct vertices of H such that the sub-hypergraph of H induced by the set
{u1,u2,u3,u4,u5,u6}
consists of hyperedges
{u1,u2,u3,u4}, {u2,u3,u4,u5}, {u3,u4,u5,u6};
there is a directed edge from vertex
(u1,u2,u3,u4,u5,u6)
of D6(H) to vertex
(v1,v2,v3,v4,v5,v6)
of D6(H) if and only if
v1=u2, v2=u3, v3=u4, v4=u5, v5=u6.

Trivially, membership in C can be tested in polynomial time; trivially, no 4-uniform hypergraph in C contains an induced odd ring; a proof that the P4-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 P4-structure contains no induced odd ring):

The P4-structure of a graph F with vertices
u1,u2,u3,u4,u5,u6
consists of hyperedges
{u1,u2,u3,u4}, {u2,u3,u4,u5}, {u3,u4,u5,u6}

only if F is isomorphic (as an unlabeled graph) with one of the following six graphs:

  1. F1 is the path P6;

  2. F2 is the complement of F1;

  3. F3 consists of vertices a,b,c,d,e,f and edges ab,bc,cd,eb,fb,fc,fe;

  4. F4 is the complement of F3;

  5. F5 consists of vertices a,b,c,d,e,f and edges ab,bc,cd,de,fb,fc;

  6. F6 is the complement of F5.
Now consider an arbitrary graph G and let H denote its P4-structure; we shall say that a vertex
(u1,u2,u3,u4,u5,u6)
of D6(H) is of type i if the subgraph of G induced by
{u1,u2,u3,u4,u5,u6}
is isomorphic with Fi. 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 P4-structure contains no induced odd ring) is this:
Each vertex of D6(H) with nonzero in-degree and nonzero out-degree has one of the following four properties:
It follows that
each strongly connected component of D6(H) with at least two vertices has one of the following three properties:

Finally, assuming that G is a basic Berge graph, we shall verify that all strongly connected components of D6(H) are bipartite. Since P4-structure of G is invariant under complementation of G, we may distinguish between three cases.

Case 1: G is bipartite.

Since F2 is not bipartite, we only need to two-color each strongly connected component of D6(H) whose vertices are of type 1. This can be done by giving each of these vertices,

(u1,u2,u3,u4,u5,u6),
the color of u1 in G.

Case 2: G is the line-graph of a bipartite graph.

The two-coloring of the vertices of the bipartite graph induces a two-coloring of the edges of G such that the two edges of any induced P3 in G have distinct colors. Since F2 is not a line-graph of a bipartite graph, we only need to two-color each strongly connected component of D6(H) whose vertices are of type 1. This can be done by giving each of these vertices,

(u1,u2,u3,u4,u5,u6),
the color of the edge u1u2 in G.

Case 3: G is a double split graph.

By definition, G has 2m+2n  (m,n>1)  distinct vertices,

a1,...,am, b1,...,bm, c1,...,cn, d1,...,dn,
and An exhaustive search shows that each vertex
(u1,u2,u3,u4,u5,u6)
of D6(H) that is of type 1 must have
u1,u3,u4,u6   in   {a1,...,am,b1,...,bm}
and
u2,u5   in   {c1,...,cn,d1,...,dn};
it follows that no two vertices of type 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 P4-structures of graphs:

Other papers on the P4-structure include:

To the table of contents

5. PARITY PAIRS AND PERFECTLY CONTRACTILE 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 H-perfectness of graphs, Bonn Workshop on Combinatorial Optimization (Bonn, 1980), Ann. Discrete Math., 16, North-Holland, Amsterdam-New York, 1982, pp. 83--95. MR 84f:05076) and H. Meyniel (A new property of critical imperfect graphs and some consequences, European J. Combin. 8 (1987), 313--316. 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), 222--230. MR 91j:05042) defined an even-contractile graph as any graph G for which there is a sequence

G0, G1, ..., Gk
such that and he defined a perfectly contractile graph as any graph G such that all induced subgraphs of G are even-contractile. (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 vertex-disjoint triangles and three vertex-disjoint 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), 85--92. MR 92m:68040a Corrigendum: Discrete Math. 102 (1992), 109. MR 92m:68040b) has proved that it is coNP-complete 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 polynomial-time algorithm to determine
if a perfect graph contains an even pair.
Problem 5.4. Design a polynomial-time 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

and in

To the table of contents

6. GRAPHS WITHOUT ODD HOLES
(AND GRAPHS WITHOUT EVEN HOLES)

Problems 6.1--6.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), 413--441. MR 89e:05089).

Problem 6.1. Prove the existence of a function g such that
every graph G with no odd hole has chromatic number at most g(omega(G)).
Guoli 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 K4.
Problem 6.2. For all positive integers k, prove the existence of a function gk such that every graph G with no odd hole longer than k has chromatic number at most gk(omega(G)).
Problem 6.3. For all positive integers k, prove the existence of a function hk such that every graph G with no hole longer than k has chromatic number at most hk(omega(G)).

Chính Hoàng and Colin McDiarmid (On the divisibility of graphs, Discrete Math. 242 (2002), 145--156. MR 1 874 761) say that a graph is 2-divisible if, for each of its induced subgraphs F, the vertex-set of F can be partitioned into subsets S1 and S2 in such a way that every largest clique in F meets both S1 and S2. Trivially, no odd hole is 2-divisible, and so every 2-divisible graph is odd-hole-free; Hoàng and McDiarmid conjectured the converse:

Conjecture 6.4. Every odd-hole-free graph is 2-divisible.
Hoàng and McDiarmid proved Conjecture 6.4. for claw-free graphs and noted that it also holds for graphs without K4 (since g(3)=4 in Problem 6.1).

Can something similar be said about graphs without even holes? The notion of 2-divisibility generalizes: Hoàng and McDiarmid say that a graph is k-divisible if, for each of its induced subgraphs F, the vertex-set of F can be partitioned into subsets S1, S2, ..., Sk in such a way that no Si contains a largest clique in F.

Conjecture 6.5. (Hoàng)   Every even-hole-free graph is 3-divisible.
Conjecture 6.6. (Hoàng)   Every even-hole-free graph G is colorable by
2·omega(G)-1
colors.
Conjecture 6.6 implies Conjecture 6.5: more generally, if G is a graph and k is an integer such that
k·(omega(G)-1) >= chi(G),
then G is k-divisible.

The following conjecture comes from Hayward and Reed (Forbidding holes and antiholes, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A . Reed, eds.), Wiley, 2001, pp. 113--137. MR 1 861 360):

Conjecture 6.7. Every even-hole-free 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ć (Even-hole-free graphs. II. Recognition algorithm. J. Graph Theory 40 (2002), 238--266) designed a polynomial algorithm to recognize even-hole-free graphs.

Problem 6.8. Design a polynomial algorithm to recognize odd-hole-free graphs.

To the table of contents

7. INTERSECTION GRAPHS

Problems 7.1--7.6 were contributed by Zsolt Tuza before the 1993 workshop (see also Tuza, Perfect triangle families, Bull. London Math. Soc. 26 (1994), 321--324. MR 96b:05083).

Problem 7.1. For every (undirected) graph G, let H1(G) denote the graph whose vertices are the triangles in G, two vertices of H1(G) being adjacent if and only if the corresponding triangles in G share an edge.
For which graphs G is H1(G) perfect?
In a slightly related paper, Akiyama and Chvátal (Packing paths perfectly, Discrete Math. 85 (1990), 247--255. MR 92a:68114) studied graphs H'(G) whose vertices are (not necessarily induced) paths P3 in G, two vertices of H'(G) being adjacent if and only if the corresponding P3'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 k-line graphs and k-total graphs, J. Graph Theory 17 (1993), 65--73. MR 94b:05083.
Problem 7.2. For every directed graph G, let H2(G) denote the graph whose vertices are the transitive triangles in G, two vertices of H2(G) being adjacent if and only if the corresponding triangles in G share an arc.
For which graphs G is H2(G) perfect?
Problem 7.3. For every directed graph G, let H3(G) denote the graph whose vertices are the cyclic triangles in G, two vertices of H3(G) being adjacent if and only if the corresponding triangles in G share an arc.
For which graphs G is H3(G) perfect?
Problem 7.4. Charaterize graphs H such that
H=H1(G) for some graph G.
Problem 7.5. Charaterize graphs H such that
H=H2(G) for some directed graph G.
Problem 7.6. Charaterize graphs H such that
H=H3(G) for some directed graph G.
If G is a planar oriented graph, then H3(G) is known to be (K4-e)-free Berge graph, and hence perfect.

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, 267--287. 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, H1(G) is the (K2,K3)-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.

To the table of contents

8. q-PERFECT GRAPHS

When q is a positive integer, alphaq(G) denotes the largest number of vertices of G that can by colored with only q colors; the q-norm of a family of sets C1,C2, ... ,Ck is the sum of the k numbers min{|Cj|,q}, and thetaq(G) is the smallest q-norm of a family C1,C2, ... ,Ck of cliques in G whose union covers all the vertices; a graph is called q-perfect if, and only if, alphaq(F)=thetaq(F) for all its induced subgraphs F. This concept was introduced by Lovász (Perfect graphs, Selected topics in graph theory (L. M. Beineke and R. L. Wilson, eds.), 2, Academic Press, London-New York, 1983, pp. 55--87. MR 86h:05053).

The following problems were contributed to the 1993 workshop by Claude Berge.

Problem 8.1 Characterize 2-perfect graphs.
Problem 8.2. Is it true that every minimal not-3-colorable 3-perfect graph is perfect?
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 2-perfect; see C. Berge, The q-perfect 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, North-Holland, Amsterdam, 1992, pp.67--75. MR 94d:05110 and C. Berge, The q-perfect graphs. II.Combinatorics 92 (Catania, 1992), Matematiche (Catania) 47 (1992), 205--211 (1993). MR 95h:05126 and C. Berge, The q-perfect graphs. Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., Wiley, New York, 1995, pp.47--62. MR 97c:05060.

To the table of contents